是自定义输入迷宫,起点为左上角,终点为右下角
时间: 2024-02-11 18:09:08 浏览: 64
指定出口和入口的迷宫
好的,那么根据您的要求,我提供如下 C 语言代码,实现迷宫问题的求解。请注意,代码中的注释会帮助您理解程序的执行过程。在程序中,我们使用了深度优先搜索(DFS)算法来求解迷宫问题。
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 1000 // 迷宫的最大行数
#define MAX_M 1000 // 迷宫的最大列数
int n, m; // 迷宫的行数和列数
char maze[MAX_N][MAX_M + 1]; // 迷宫的字符数组表示
int visited[MAX_N][MAX_M]; // 标记每个位置是否已经访问过
int dx[4] = {0, 0, 1, -1}; // 行走的四个方向
int dy[4] = {1, -1, 0, 0};
int dfs(int x, int y, char path[], int len) {
if (x == n - 1 && y == m - 1) { // 到达终点
path[len] = '\0'; // 将字符串结尾符置为'\0'
printf("%s\n", path); // 输出路径
return 1; // 返回1表示已找到一条路径
}
visited[x][y] = 1; // 标记当前位置已访问
for (int i = 0; i < 4; i++) { // 枚举四个方向
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] == '0' && !visited[nx][ny]) {
// 位置合法且为0且未访问过
path[len] = i == 0 ? 'R' : (i == 1 ? 'L' : (i == 2 ? 'D' : 'U')); // 记录路径
if (dfs(nx, ny, path, len+1)) { // 递归搜索
return 1; // 如果已经找到一条路径,直接返回1
}
}
}
visited[x][y] = 0; // 标记当前位置未访问
return 0; // 返回0表示未找到路径
}
int main() {
// 输入迷宫
n = 0;
while (fgets(maze[n], MAX_M + 1, stdin) && maze[n][0] != '\n') {
n++;
}
m = strlen(maze[0]) - 1;
// 初始化visited数组
memset(visited, 0, sizeof(visited));
// 搜索迷宫
char path[MAX_N * MAX_M + 1];
if (!dfs(0, 0, path, 0)) {
printf("NO PASS!\n"); // 没有找到路径
}
return 0;
}
```
您可以将以上代码保存到一个名为 `maze.c` 的文件中,并使用 C 语言编译器进行编译,在命令行中运行程序即可。请注意,为了方便起见,以上代码并没有进行输入检查,如果您输入的迷宫格式不正确,程序可能会出现错误。
阅读全文