有一 8×8 的迷宫图,其中 O表示通路方块,X 表示障碍方块。假设入口位置为 (0,0),出口为右下角方块位置 (7,7)。设计一个程序求指定入口到出口的一条迷宫路径。要求输入8 行,每行 8个字符表示迷宫。 输入保证至少存在一条合法路径。输出8 行,每行 8 个字符,空格表示所选路径。用C语言编程
时间: 2024-02-13 12:06:58 浏览: 51
很抱歉,刚才的代码有误,这里提供一个正确的实现,仍然使用深度优先搜索算法。
```c
#include <stdio.h>
#include <stdbool.h>
#define N 8
char maze[N][N]; // 迷宫地图
bool visited[N][N]; // 标记是否访问过
int path[N][N]; // 记录路径
bool dfs(int x, int y) {
visited[x][y] = true; // 标记为已访问
if (x == N-1 && y == N-1) { // 到达终点
return true;
}
if (maze[x][y] == 'X' || visited[x][y]) { // 障碍或已访问过
return false;
}
if (x > 0 && dfs(x-1, y)) { // 向上走
path[x][y] = 1;
return true;
}
if (y < N-1 && dfs(x, y+1)) { // 向右走
path[x][y] = 1;
return true;
}
if (x < N-1 && dfs(x+1, y)) { // 向下走
path[x][y] = 1;
return true;
}
if (y > 0 && dfs(x, y-1)) { // 向左走
path[x][y] = 1;
return true;
}
return false; // 无路可走
}
int main() {
// 读入迷宫地图
for (int i = 0; i < N; i++) {
scanf("%s", maze[i]);
}
// 搜索迷宫路径
dfs(0, 0);
// 输出迷宫路径
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (path[i][j] == 1) {
printf(" "); // 输出空格表示路径
} else {
printf("%c ", maze[i][j]); // 输出迷宫地图
}
}
printf("\n");
}
return 0;
}
```
在这个实现中,我们使用了一个 `visited` 数组来标记是否访问过一个方块,避免重复访问。同时,我们使用了一个 `path` 数组来记录路径,其中 1 表示该方块在路径上,0 表示不在路径上。
输入和输出都和上一个问题一样,这里不再赘述。
阅读全文