问题描述:以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。用C语言
时间: 2023-08-31 21:04:56 浏览: 160
以下是一个使用DFS深度优先搜索算法求解迷宫通路的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_ROW 100
#define MAX_COL 100
int maze[MAX_ROW][MAX_COL];
int mark[MAX_ROW][MAX_COL]; // 标记数组,标记某个位置是否已经访问过
int rows, cols; // 迷宫的行数和列数
// DFS函数,寻找从(x1, y1)到(x2, y2)的路径
int dfs(int x1, int y1, int x2, int y2) {
if (x1 < 0 || x1 >= rows || y1 < 0 || y1 >= cols) // 越界
return 0;
if (maze[x1][y1] == 1) // 障碍
return 0;
if (mark[x1][y1] == 1) // 已经访问过
return 0;
if (x1 == x2 && y1 == y2) { // 找到了终点
printf("(%d,%d)", x1, y1);
return 1;
}
mark[x1][y1] = 1; // 标记为已访问
if (dfs(x1-1, y1, x2, y2) == 1) { // 向上走
printf("(%d,%d)", x1, y1);
return 1;
}
if (dfs(x1+1, y1, x2, y2) == 1) { // 向下走
printf("(%d,%d)", x1, y1);
return 1;
}
if (dfs(x1, y1-1, x2, y2) == 1) { // 向左走
printf("(%d,%d)", x1, y1);
return 1;
}
if (dfs(x1, y1+1, x2, y2) == 1) { // 向右走
printf("(%d,%d)", x1, y1);
return 1;
}
return 0; // 没有找到通路
}
int main() {
int i, j;
scanf("%d %d", &rows, &cols);
for (i = 0; i < rows; i++) {
for (j = 0; j < cols; j++) {
scanf("%d", &maze[i][j]);
mark[i][j] = 0; // 初始化标记数组
}
}
if (dfs(0, 0, rows-1, cols-1) == 0) // 从入口(0,0)到出口(rows-1,cols-1)
printf("No path found.\n");
return 0;
}
```
程序中,dfs函数使用递归实现DFS深度优先搜索算法,寻找从(x1, y1)到(x2, y2)的路径。如果找到了通路,就输出路径并返回1;否则返回0。在主函数中,先读入迷宫,然后调用dfs函数查找通路。如果没有找到通路,就输出"No path found."。
阅读全文