以一个m×n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍,设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论,用c语言来实现
时间: 2023-12-07 08:05:29 浏览: 147
以一个mXn的长方阵表示迷宫, 0和1分别表示迷宫中的通路和障碍 设 计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路
以下是一个简单的深度优先搜索算法实现,用于找到从迷宫的起点到终点的路径。其中,迷宫中的0表示通路,1表示障碍物。
```c
#include <stdio.h>
#include <stdlib.h>
#define ROWS 10
#define COLS 10
int maze[ROWS][COLS] = {
{0, 1, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 1, 0, 1, 1, 1, 0, 1, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 0},
{1, 1, 1, 1, 0, 1, 0, 1, 1, 0},
{0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 1, 0, 1, 1, 0, 1, 1},
{0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 0, 1, 0, 1, 1, 1},
{0, 1, 0, 0, 0, 1, 0, 0, 0, 0},
{0, 1, 0, 1, 0, 1, 0, 1, 0, 0}
};
int visited[ROWS][COLS] = {0};
int path[ROWS * COLS][2];
int cnt = 0;
int dfs(int x, int y) {
if (x < 0 || x >= ROWS || y < 0 || y >= COLS) {
return 0;
}
if (maze[x][y] == 1 || visited[x][y] == 1) {
return 0;
}
if (x == ROWS - 1 && y == COLS - 1) {
path[cnt][0] = x;
path[cnt][1] = y;
cnt++;
return 1;
}
visited[x][y] = 1;
if (dfs(x, y + 1) || dfs(x + 1, y) || dfs(x, y - 1) || dfs(x - 1, y)) {
path[cnt][0] = x;
path[cnt][1] = y;
cnt++;
return 1;
}
return 0;
}
int main() {
dfs(0, 0);
if (cnt == 0) {
printf("No path found.\n");
} else {
printf("Path found:\n");
for (int i = cnt - 1; i >= 0; i--) {
printf("(%d, %d) ", path[i][0], path[i][1]);
}
printf("\n");
}
return 0;
}
```
该程序采用深度优先搜索算法,从起点开始向四个方向探索,如果发现一个新的点可以到达,则继续递归搜索该点,直到到达终点或者无法继续搜索。在搜索过程中,将已经访问过的点标记为visited,以防止重复访问。如果找到了一条路径,则将路径上的点保存在path数组中,最后按照倒序输出即可。如果没有找到路径,则输出"No path found."。
阅读全文