用C语言问题描述:以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。
时间: 2023-08-31 10:05:05 浏览: 37
这道题可以使用深度优先搜索(DFS)算法来解决。
首先,我们定义一个结构体来表示迷宫中的每个点:
```c
struct Point {
int x; // 横坐标
int y; // 纵坐标
};
```
接下来,我们需要定义一个函数来判断某个点是否在迷宫中:
```c
int isValid(int x, int y, int m, int n, int maze[][n]) {
if (x < 0 || x >= m || y < 0 || y >= n || maze[x][y] == 1) {
return 0; // 越界或者是障碍物,返回0
}
return 1; // 合法的点,返回1
}
```
接下来,我们定义一个递归函数来进行深度优先搜索:
```c
int dfs(struct Point cur, struct Point end, int m, int n, int maze[][n], int visited[][n], struct Point path[], int* pathLen) {
if (cur.x == end.x && cur.y == end.y) {
// 如果当前点是终点,说明找到了一条可行路径
path[*pathLen] = cur;
(*pathLen)++;
return 1;
}
visited[cur.x][cur.y] = 1; // 标记当前点已经访问过了
if (isValid(cur.x-1, cur.y, m, n, maze) && !visited[cur.x-1][cur.y]) {
// 尝试向上走
struct Point next = {cur.x-1, cur.y};
if (dfs(next, end, m, n, maze, visited, path, pathLen)) {
// 如果从这个方向找到了一条可行路径,将当前点加入路径中
path[*pathLen] = cur;
(*pathLen)++;
return 1;
}
}
if (isValid(cur.x+1, cur.y, m, n, maze) && !visited[cur.x+1][cur.y]) {
// 尝试向下走
struct Point next = {cur.x+1, cur.y};
if (dfs(next, end, m, n, maze, visited, path, pathLen)) {
path[*pathLen] = cur;
(*pathLen)++;
return 1;
}
}
if (isValid(cur.x, cur.y-1, m, n, maze) && !visited[cur.x][cur.y-1]) {
// 尝试向左走
struct Point next = {cur.x, cur.y-1};
if (dfs(next, end, m, n, maze, visited, path, pathLen)) {
path[*pathLen] = cur;
(*pathLen)++;
return 1;
}
}
if (isValid(cur.x, cur.y+1, m, n, maze) && !visited[cur.x][cur.y+1]) {
// 尝试向右走
struct Point next = {cur.x, cur.y+1};
if (dfs(next, end, m, n, maze, visited, path, pathLen)) {
path[*pathLen] = cur;
(*pathLen)++;
return 1;
}
}
return 0; // 没有找到可行路径
}
```
最后,我们可以定义一个主函数来测试上面的算法:
```c
int main() {
int maze[5][5] = {
{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[5][5] = {0};
struct Point start = {0, 0};
struct Point end = {4, 4};
struct Point path[25];
int pathLen = 0;
if (dfs(start, end, 5, 5, maze, visited, path, &pathLen)) {
// 如果找到了可行路径,输出路径
for (int i = pathLen-1; i >= 0; i--) {
printf("(%d, %d)\n", path[i].x, path[i].y);
}
} else {
printf("No path found!\n");
}
return 0;
}
```
这个程序的输出结果应该是:
```
(0, 0)
(0, 1)
(1, 1)
(2, 1)
(2, 0)
(3, 0)
(4, 0)
(4, 1)
(4, 2)
(3, 2)
(2, 2)
(1, 2)
(1, 3)
(1, 4)
(4, 4)
```