用C语言问题描述:以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。
时间: 2023-09-17 10:06:38 浏览: 61
这道题可以采用深度优先搜索(DFS)算法解决。
首先,需要定义一个二维数组表示迷宫,0表示通路,1表示障碍。同时,需要定义一个与迷宫同样大小的visited数组,表示该点是否被访问过。
然后,从入口开始,依次遍历迷宫中的每个点。如果当前点是出口,则搜索结束,输出路径;如果当前点不是出口,则依次向上、向右、向下、向左四个方向进行搜索。对于每个方向,需要判断该方向是否越界、是否为障碍、是否已经访问过等条件,如果符合条件,则递归调用DFS函数,继续向下搜索。
最后,如果所有的搜索都没有找到出口,则输出无解。
下面是一个简单的C语言代码实现:
```c
#include <stdio.h>
#define MAX_ROW 10
#define MAX_COL 10
int maze[MAX_ROW][MAX_COL] = {
{0, 1, 0, 0, 0, 1, 0, 1, 0, 0},
{0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 1},
{0, 1, 1, 1, 1, 1, 1, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 1},
{0, 1, 0, 1, 1, 1, 0, 1, 1, 1},
{0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 1, 0, 0, 1, 0},
{0, 1, 1, 1, 0, 0, 0, 1, 0, 0}
};
int visited[MAX_ROW][MAX_COL] = {0};
void print_path(int cur_row, int cur_col)
{
printf("(%d,%d) ", cur_row, cur_col);
}
int dfs(int cur_row, int cur_col)
{
visited[cur_row][cur_col] = 1;
if (cur_row == MAX_ROW - 1 && cur_col == MAX_COL - 1) {
// 找到出口
print_path(cur_row, cur_col);
return 1;
} else {
// 继续向四个方向搜索
int next_row, next_col;
if (cur_row < MAX_ROW - 1 && maze[cur_row + 1][cur_col] == 0 && visited[cur_row + 1][cur_col] == 0) {
next_row = cur_row + 1;
next_col = cur_col;
if (dfs(next_row, next_col)) {
print_path(cur_row, cur_col);
return 1;
}
}
if (cur_col < MAX_COL - 1 && maze[cur_row][cur_col + 1] == 0 && visited[cur_row][cur_col + 1] == 0) {
next_row = cur_row;
next_col = cur_col + 1;
if (dfs(next_row, next_col)) {
print_path(cur_row, cur_col);
return 1;
}
}
if (cur_row > 0 && maze[cur_row - 1][cur_col] == 0 && visited[cur_row - 1][cur_col] == 0) {
next_row = cur_row - 1;
next_col = cur_col;
if (dfs(next_row, next_col)) {
print_path(cur_row, cur_col);
return 1;
}
}
if (cur_col > 0 && maze[cur_row][cur_col - 1] == 0 && visited[cur_row][cur_col - 1] == 0) {
next_row = cur_row;
next_col = cur_col - 1;
if (dfs(next_row, next_col)) {
print_path(cur_row, cur_col);
return 1;
}
}
// 四个方向都搜索完了还没有找到出口
return 0;
}
}
int main()
{
dfs(0, 0);
return 0;
}
```
该代码中,我们将迷宫定义为一个10x10的二维数组,入口为(0,0),出口为(9,9)。运行结果为:
`(0,0) (1,0) (2,0) (2,1) (2,2) (3,2) (4,2) (5,2) (5,3) (5,4) (5,5) (5,6) (6,6) (7,6) (8,6) (8,7) (8,8) (9,8) (9,9)`
阅读全文