c采用递归算法求解迷宫问题,并输出从入口到出口的所有迷宫路径。
时间: 2023-12-10 15:38:22 浏览: 69
好的,以下是基于递归算法的迷宫问题求解代码示例:
```
#include <stdio.h>
#define ROW 5
#define COL 5
int map[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 path[ROW*COL][2]; // 存储路径
int path_len = 0; // 路径长度
int find_path(int x, int y)
{
if (x < 0 || x >= ROW || y < 0 || y >= COL || map[x][y] == 1) {
// 当前节点越界或已访问过,返回失败
return 0;
}
if (x == ROW-1 && y == COL-1) {
// 已到达终点,记录路径并返回成功
path[path_len][0] = x;
path[path_len][1] = y;
path_len++;
return 1;
}
// 标记当前节点已访问
map[x][y] = 1;
// 递归查找相邻节点
if (find_path(x+1, y) || find_path(x-1, y) || find_path(x, y+1) || find_path(x, y-1)) {
// 当前节点能够到达终点,记录路径并返回成功
path[path_len][0] = x;
path[path_len][1] = y;
path_len++;
return 1;
}
// 当前节点不能到达终点,回溯并返回失败
map[x][y] = 0;
return 0;
}
int main()
{
int i, j;
// 打印地图
printf("Map:\n");
for (i = 0; i < ROW; i++) {
for (j = 0; j < COL; j++) {
printf("%d ", map[i][j]);
}
printf("\n");
}
// 查找路径
if (find_path(0, 0)) {
// 打印路径
printf("Path:\n");
for (i = path_len-1; i >= 0; i--) {
printf("(%d,%d)\n", path[i][0], path[i][1]);
}
} else {
printf("No path found!\n");
}
return 0;
}
```
该代码中,`map`数组存储了迷宫地图,其中0表示可通过的路,1表示障碍物。`path`数组用于存储路径,`path_len`记录路径长度。`find_path`函数是递归查找路径的核心函数。首先判断当前节点是否越界或已访问过,如果是则返回失败;如果当前节点已到达终点,则记录路径并返回成功;否则标记当前节点已访问,递归查找相邻节点,如果某个相邻节点能够到达终点,则记录路径并返回成功。如果所有相邻节点都不能到达终点,则回溯并返回失败。在主函数中,先打印地图,然后调用`find_path`函数查找路径,最后打印路径。
阅读全文