帮我编一个C语言的迷宫求解
时间: 2023-05-25 11:02:41 浏览: 55
下面是一个简单的C语言迷宫求解程序:
```
#include <stdio.h>
#define ROW 8 // 迷宫行数
#define COL 8 // 迷宫列数
int map[ROW][COL] = { // 迷宫地图,1表示墙,0表示通路
{1, 1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 0, 0, 0, 1},
{1, 0, 1, 1, 0, 1, 0, 1},
{1, 0, 1, 0, 0, 1, 0, 1},
{1, 0, 1, 0, 1, 1, 0, 1},
{1, 0, 1, 0, 0, 0, 0, 1},
{1, 0, 0, 0, 1, 1, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1}
};
int visited[ROW][COL]; // 记录已访问过的位置,1表示已访问
int path[ROW * COL][2]; // 记录路径,path[i][0]表示第i个位置的横坐标,path[i][1]表示纵坐标
int path_count = 0; // 记录路径长度
void print_path() { // 打印路径
int i;
printf("路径:");
for (i = 0; i < path_count; i++) {
printf("(%d, %d) ", path[i][0], path[i][1]);
}
printf("\n");
}
int dfs(int x, int y) { // 深度优先搜索
if (x == ROW - 2 && y == COL - 2) { // 到达终点
return 1;
}
visited[x][y] = 1; // 将当前位置标记为已访问
if (x > 1 && !visited[x-1][y] && !map[x-1][y]) { // 判断上方位置是否可达并未访问过
path[path_count][0] = x - 1;
path[path_count][1] = y;
path_count++;
if (dfs(x-1, y)) {
return 1;
}
path_count--;
}
if (y < COL - 3 && !visited[x][y+1] && !map[x][y+1]) { // 判断右方位置是否可达并未访问过
path[path_count][0] = x;
path[path_count][1] = y + 1;
path_count++;
if (dfs(x, y+1)) {
return 1;
}
path_count--;
}
if (x < ROW - 3 && !visited[x+1][y] && !map[x+1][y]) { // 判断下方位置是否可达并未访问过
path[path_count][0] = x + 1;
path[path_count][1] = y;
path_count++;
if (dfs(x+1, y)) {
return 1;
}
path_count--;
}
if (y > 1 && !visited[x][y-1] && !map[x][y-1]) { // 判断左方位置是否可达并未访问过
path[path_count][0] = x;
path[path_count][1] = y - 1;
path_count++;
if (dfs(x, y-1)) {
return 1;
}
path_count--;
}
visited[x][y] = 0; // 回溯,将当前位置标记为未访问
return 0;
}
int main() {
int i, j;
for (i = 0; i < ROW; i++) { // 初始化visited数组
for (j = 0; j < COL; j++) {
visited[i][j] = 0;
}
}
if (dfs(1, 1)) {
print_path();
} else {
printf("无解\n");
}
return 0;
}
```
程序使用深度优先搜索算法,从起点(1, 1)开始搜索,每次向上、下、左、右四个方向扩展,如果扩展过程中到达终点(ROW-2, COL-2),则搜索成功,记录路径。如果所有扩展点均已访问或无法扩展,则回溯到上一个访问过的点再继续扩展。路径由path数组记录,path_count记录路径长度。具体实现中,使用visited数组记录已访问过的位置,1表示已访问。如果一个位置未访问过,且不是墙,可以扩展到该位置。最终,如果有解,则打印路径;否则,在屏幕上显示“无解”。