C语言实现,从标准输入读取迷宫,求解出给定起点和终点间的路径,路径由 L、R、D、U 组成,并输出路径。如果起点到终点没有路径,则输出“NO PASS!”。
时间: 2024-01-17 10:04:37 浏览: 31
好的,以下是使用 C 语言实现的代码:
```c
#include <stdio.h>
#include <stdbool.h>
// 定义迷宫的四个方向
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
char direction[] = {'R', 'L', 'D', 'U'};
// 读取迷宫
#define MAXN 100
char maze[MAXN][MAXN];
int n, m;
// 定义起点和终点
int start_x, start_y, end_x, end_y;
// 记录走过的路径
char path[MAXN * MAXN];
int path_len = 0;
// 定义 DFS 搜索函数
bool dfs(int x, int y) {
// 判断是否到达终点
if (x == end_x && y == end_y) {
return true;
}
// 标记当前点已经访问过
maze[x][y] = '#';
// 尝试往四个方向走
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] == '.') {
if (dfs(nx, ny)) {
path[path_len++] = direction[i];
return true;
}
}
}
// 如果四个方向都走不通,则回溯
return false;
}
int main() {
// 读入迷宫
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%s", maze[i]);
}
// 读入起点和终点
scanf("%d%d%d%d", &start_x, &start_y, &end_x, &end_y);
// 调用 DFS 搜索函数
if (dfs(start_x, start_y)) {
for (int i = path_len - 1; i >= 0; i--) {
printf("%c", path[i]);
}
printf("\n");
} else {
printf("NO PASS!\n");
}
return 0;
}
```
这个程序的时间复杂度也是 $O(nm)$,其中 $n$ 和 $m$ 分别为迷宫的高和宽。
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)