有一 8 \times 88×8 的迷宫图,其中 OO 表示通路方块,XX 表示障碍方块。假设入口位置为 (0,0)(0,0),出口为右下角方块位置 (7,7)(7,7)。设计一个程序求指定入口到出口的一条迷宫路径。(C语言)
时间: 2024-02-17 22:01:09 浏览: 138
好的,这是一个比较经典的迷宫问题,可以使用深度优先搜索或广度优先搜索来解决。以下是一个基于深度优先搜索的 C 语言实现:
```c
#include <stdio.h>
#include <stdbool.h>
#define ROWS 8
#define COLS 8
char maze[ROWS][COLS] = {
{'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O'},
{'O', 'X', 'O', 'X', 'O', 'X', 'O', 'O'},
{'O', 'O', 'O', 'X', 'O', 'O', 'O', 'O'},
{'O', 'X', 'O', 'O', 'O', 'X', 'O', 'O'},
{'O', 'O', 'X', 'O', 'O', 'O', 'O', 'O'},
{'O', 'X', 'O', 'X', 'O', 'X', 'X', 'O'},
{'O', 'X', 'O', 'O', 'O', 'O', 'O', 'O'},
{'O', 'X', 'X', 'X', 'X', 'X', 'X', 'O'},
};
bool visited[ROWS][COLS];
bool dfs(int x, int y) {
if (x == ROWS - 1 && y == COLS - 1) { // 到达终点
return true;
}
visited[x][y] = true;
if (x - 1 >= 0 && maze[x - 1][y] == 'O' && !visited[x - 1][y]) { // 上
if (dfs(x - 1, y)) {
printf("(%d,%d) ", x - 1, y);
return true;
}
}
if (x + 1 < ROWS && maze[x + 1][y] == 'O' && !visited[x + 1][y]) { // 下
if (dfs(x + 1, y)) {
printf("(%d,%d) ", x + 1, y);
return true;
}
}
if (y - 1 >= 0 && maze[x][y - 1] == 'O' && !visited[x][y - 1]) { // 左
if (dfs(x, y - 1)) {
printf("(%d,%d) ", x, y - 1);
return true;
}
}
if (y + 1 < COLS && maze[x][y + 1] == 'O' && !visited[x][y + 1]) { // 右
if (dfs(x, y + 1)) {
printf("(%d,%d) ", x, y + 1);
return true;
}
}
return false;
}
int main() {
int x = 0, y = 0;
printf("迷宫路径为:\n");
if (dfs(x, y)) {
printf("(7,7)\n");
} else {
printf("不存在路径\n");
}
return 0;
}
```
该程序使用了 `visited` 数组来记录某个方块是否已经被访问过,防止重复访问。在 `dfs` 函数中,首先判断当前方块是否是终点,如果是则返回 `true`;否则标记当前方块已访问,并分别递归访问上、下、左、右四个方向的方块,如果找到一条通路则输出路径并返回 `true`,否则返回 `false`。在 `main` 函数中调用 `dfs` 函数,并输出迷宫路径。
阅读全文