dfs算法c语言迷宫问题
时间: 2023-07-26 20:33:12 浏览: 56
好的,这是一个关于使用深度优先搜索(DFS)算法解决迷宫问题的C语言实现示例:
```
#include <stdio.h>
#define ROW 5
#define COL 5
int maze[ROW][COL] = {
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 1, 0}
};
int visited[ROW][COL] = {0};
int dfs(int x, int y) {
if (x < 0 || x >= ROW || y < 0 || y >= COL) { // 当前位置越界
return 0;
}
if (maze[x][y] == 1 || visited[x][y] == 1) { // 当前位置是障碍或已经访问过
return 0;
}
if (x == ROW - 1 && y == COL - 1) { // 到达终点
return 1;
}
visited[x][y] = 1; // 标记为已访问
if (dfs(x + 1, y) || dfs(x - 1, y) || dfs(x, y + 1) || dfs(x, y - 1)) { // 搜索四个方向
return 1;
}
return 0;
}
int main() {
if (dfs(0, 0)) {
printf("迷宫有解");
} else {
printf("迷宫无解");
}
return 0;
}
```
这个迷宫是一个5x5的矩阵,0表示可以通过,1表示障碍物,起点为(0,0),终点为(4,4)。使用DFS算法遍历每个可达点,若能到达终点则返回1,否则返回0。