广度优先搜索算法 - 迷宫找路

这是一个提问者的提出的问题： 连接

数据结构算法，用C语言完成，
迷宫寻路：以一个的长方阵表示迷宫，用0和1分别表示迷宫中的通路和障碍，将迷宫的长方阵存储在相关数据文件中，迷宫数据从该文件中读取。找到一条从入口到出口的通路，或得到没有通路的结论。将找到的通路以三元组的形式输出，表示经过节点的坐标，表示从入口出发达到该节点的距离，每走一步距离加1。最终输出全部通路，并统计路径距离。

经过我们的讨论，我决定重新实现我之前的算法！以下是完整内容

1 思考问题

1.1 这个迷宫需不需要指定入口和出口？

我之前提供的算法是默认起点为左上角，终点为右下角。如果你的迷宫入口或者出口为“1”，这将导致无法找到路径；这也就解释了，为什么你的迷宫会出现这样的结果！

根据的你的提供迷宫，我猜测，你的想法可能是：这个迷宫不需要指定出口和入口，而是让程序自己找。
这样的情况算法实现起来会更复杂，更困难，需要加很多个约束条（比如，入口不能是出口等）！
根据之前的沟通，我感觉您像是初学者（如果我猜错了，冒犯到您，向您道歉），应该不会一上来就挑战那么难的算法！所以这个算法应该是指定入口和出口的，这样就会让程序变得简单很多！

2 先粗略实现

2.1 源码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX_SIZE 100typedef struct {int x;int y;int distance;
} Node;void BFS(int maze[][MAX_SIZE], int n, int m, int startX, int startY, int endX, int endY) {// 定义方向数组，表示上下左右四个方向int dx[4] = { -1, 1, 0, 0 };int dy[4] = { 0, 0, -1, 1 };// 定义队列和标记数组Node queue[MAX_SIZE * MAX_SIZE];int front = 0, rear = 0;bool visited[MAX_SIZE][MAX_SIZE] = { false };Node parentMap[MAX_SIZE][MAX_SIZE];// 将起点加入队列中Node start = { startX, startY, 0 };queue[rear++] = start;visited[startX][startY] = true;// 开始广度优先搜索while (front < rear) {// 取出队列中的节点Node curr = queue[front++];// 检查是否到达终点if (curr.x == endX && curr.y == endY) {printf("Find a path: ");printf("(%d,%d,%d)", curr.x, curr.y, curr.distance);Node parent = parentMap[curr.x][curr.y];while (parent.x != startX || parent.y != startY) {printf(" <- ");printf("(%d,%d,%d)", parent.x, parent.y, parent.distance);parent = parentMap[parent.x][parent.y];}printf(" <- ");printf("(%d,%d,0)\n", startX, startY);continue;}// 访问相邻节点for (int i = 0; i < 4; i++) {int nx = curr.x + dx[i];int ny = curr.y + dy[i];if (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] == 0 && !visited[nx][ny]) {Node next = { nx, ny, curr.distance + 1 };queue[rear++] = next;visited[nx][ny] = true;parentMap[nx][ny] = curr;}}}
}int main() {// 从文件中读取迷宫数据int maze[MAX_SIZE][MAX_SIZE];int n, m;FILE *fp = fopen("maze.txt", "r");fscanf(fp, "%d%d", &n, &m);for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {fscanf(fp, "%d", &maze[i][j]);}}fclose(fp);// 确定起点和终点int startX = 0,startY = 0, endX = n - 1, endY = m - 1;// 使用广度优先搜索算法搜索最短路径BFS(maze, n, m, startX, startY, endX, endY);return 0;
}

2.2 源码解释

#define _CRT_SECURE_NO_WARNINGS

我的编译器使用的是vs2017，而我在代码中使用了fopen等函数，编译器认为：使用的是不安全的C标准库函数fopen()，建议使用更安全的fopen_s()函数来代替。但是没有必要，所以我加上了这行代码，让编译器忽略这个警告。如果你的编译器运行我之前的代码，编译没有报错，你也可以将这一行去掉。

	int startX = 0,startY = 0, endX = n - 1, endY = m - 1;

这一行是在main函数中的，他的目的就是确定迷宫的入口和出口，默认是左上到右下，你可以通过更改数值实现，自定义入口和出口。
例如：起点（0,1）；终点（6，8）

int startX = 0,startY = 1, endX = 6, endY = 7;

这里我提供一个7X9迷宫：

7 9
1 0 0 0 1 0 1 1 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 0 1 1 1
1 1 0 1 0 1 0 0 0
0 0 0 1 0 0 0 1 1
1 1 0 0 0 1 0 0 0
0 0 0 1 0 1 0 0 0

你可能注意到了，我的迷宫结构和之前提供给你的迷宫结构发生了变化，在开始处，增加了迷宫的大小“7 9”，这是告诉程序我迷宫的大小，也就是说，现在的迷宫大小我们也可以是自定义的了！
运行结果：

代码已经可以实现了！

3 优化代码

3.1 优化读取文件部分

以下是将读取迷宫数据部分的代码封装成一个函数 readMaze，并添加了判断文件是否成功打开的代码：

bool readMaze(const char *filename, int maze[][MAX_SIZE], int *n, int *m) {FILE *fp = fopen(filename, "r");if (!fp) {printf("Error: Failed to open file %s.\n", filename);return false;}fscanf(fp, "%d%d", n, m);for (int i = 0; i < *n; i++) {for (int j = 0; j < *m; j++) {fscanf(fp, "%d", &maze[i][j]);}}fclose(fp);return true;
}

然后，在 main 函数中调用该函数读取迷宫数据

int main() {int maze[MAX_SIZE][MAX_SIZE];int n, m;if (!readMaze("maze.txt", maze, &n, &m)) {return 1;}// 确定起点和终点int startX = 0, startY = 0, endX = n-1, endY = m-1;//注意：可以自定义// 使用广度优先搜索算法搜索最短路径BFS(maze, n, m, startX, startY, endX, endY);return 0;
}

这样做的好处是，将读取迷宫数据的代码封装成一个函数，可以使 main 函数更加清晰简洁，也方便在其他函数中重复使用该代码。另外，添加判断文件是否成功打开的代码，可以在打开文件失败时及时提示用户，并退出程序。

3.2 增加错误处理

1. 判断自定义的迷宫入口和出口是否合法，比如说，刚才迷宫大小为7*9，你却定义一个出口为（10,11），那么这个出口肯定是越界了
2. 以及判断你自定义迷宫入口和出口是否合法，也就是说，如果你设计迷宫入口或者出口为“1”，也是不合理的。
   一个函数实现这两个功能

bool isValidPoint(int maze[][MAX_SIZE], int n, int m, int x, int y) {if (x < 0 || x >= n || y < 0 || y >= m) {return false;}if (maze[x][y] != 0) {return false;}return true;
}

然后，我们可以在 BFS 函数和 main 函数中使用该函数来检查起点和终点的合法性。例如，在 BFS 函数中，可以将下面这行代码：

if (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] == 0 && !visited[nx][ny]) {

修改为：

if (isValidPoint(maze, n, m, nx, ny) && !visited[nx][ny]) {

在 main 函数中，可以添加以下代码来检查起点和终点的合法性：

if (!isValidPoint(maze, n, m, startX, startY)) {printf("Error: Invalid start point (%d,%d).\n", startX, startY);return 1;
}
if (!isValidPoint(maze, n, m, endX, endY)) {printf("Error: Invalid end point (%d,%d).\n", endX, endY);return 1;
}

这样，当输入的起点或终点不合法时，程序会输出错误信息并退出。
我们使用刚才的迷宫进行测试，起点设置为（0,0）
运行如下：

因为刚才的迷宫入口为1，所以给出了（0,0）位置无效的提示，其他的可以自行测试！

4 再优化-让程序变得更加灵活

4.1 用户外部可以循环输入入口和出口

输入格式为0,1英文逗号隔开

int main() {int maze[MAX_SIZE][MAX_SIZE];int n, m;if (!readMaze("maze.txt", maze, &n, &m)) {return 1;}// 从键盘输入起点和终点的坐标int startX, startY, endX, endY;while (1) {printf("Please enter the start point (x,y), or enter -1 to quit: ");int len = scanf("%d,%d", &startX, &startY);if (len == 1 && startX == -1)break;if ( len != 2) {printf("Error: Invalid input for start point.\n");continue;}if (!isValidPoint(maze, n, m, startX, startY)) {printf("Error: Invalid start point (%d,%d).\n", startX, startY);continue;}printf("Please enter the end point (x,y): ");if (scanf("%d,%d", &endX, &endY) != 2) {printf("Error: Invalid input for end point.\n");continue;}if (!isValidPoint(maze, n, m, endX, endY)) {printf("Error: Invalid end point (%d,%d).\n", endX, endY);continue;}// 使用广度优先搜索算法搜索最短路径BFS(maze, n, m, startX, startY, endX, endY);}return 0;
}

运行结果：

5 完整代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX_SIZE 100typedef struct {int x;int y;int distance;
} Node;bool isValidPoint(int maze[][MAX_SIZE], int n, int m, int x, int y) {if (x < 0 || x >= n || y < 0 || y >= m) {return false;}if (maze[x][y] != 0) {return false;}return true;
}bool readMaze(const char *filename, int maze[][MAX_SIZE], int *n, int *m) {FILE *fp = fopen(filename, "r");if (!fp) {printf("Error: Failed to open file %s.\n", filename);return false;}fscanf(fp, "%d%d", n, m);for (int i = 0; i < *n; i++) {for (int j = 0; j < *m; j++) {fscanf(fp, "%d", &maze[i][j]);}}fclose(fp);return true;
}void BFS(int maze[][MAX_SIZE], int n, int m, int startX, int startY, int endX, int endY) {// 定义方向数组，表示上下左右四个方向int dx[4] = { -1, 1, 0, 0 };int dy[4] = { 0, 0, -1, 1 };// 定义队列和标记数组Node queue[MAX_SIZE * MAX_SIZE];int front = 0, rear = 0;bool visited[MAX_SIZE][MAX_SIZE] = { false };Node parentMap[MAX_SIZE][MAX_SIZE];// 将起点加入队列中Node start = { startX, startY, 0 };queue[rear++] = start;visited[startX][startY] = true;// 开始广度优先搜索while (front < rear) {// 取出队列中的节点Node curr = queue[front++];// 检查是否到达终点if (curr.x == endX && curr.y == endY) {printf("Find a path: ");printf("(%d,%d,%d)", curr.x, curr.y, curr.distance);Node parent = parentMap[curr.x][curr.y];while (parent.x != startX || parent.y != startY) {printf(" <- ");printf("(%d,%d,%d)", parent.x, parent.y, parent.distance);parent = parentMap[parent.x][parent.y];}printf(" <- ");printf("(%d,%d,0)\n", startX, startY);continue;}// 访问相邻节点for (int i = 0; i < 4; i++) {int nx = curr.x + dx[i];int ny = curr.y + dy[i];if (isValidPoint(maze, n, m, nx, ny) && !visited[nx][ny]) {Node next = { nx, ny, curr.distance + 1 };queue[rear++] = next;visited[nx][ny] = true;parentMap[nx][ny] = curr;}}}
}int main() {int maze[MAX_SIZE][MAX_SIZE];int n, m;if (!readMaze("maze.txt", maze, &n, &m)) {return 1;}// 从键盘输入起点和终点的坐标int startX, startY, endX, endY;while (1) {printf("Please enter the start point (x,y), or enter -1 to quit: ");int len = scanf("%d,%d", &startX, &startY);if (len == 1 && startX == -1)break;if ( len != 2) {printf("Error: Invalid input for start point.\n");continue;}if (!isValidPoint(maze, n, m, startX, startY)) {printf("Error: Invalid start point (%d,%d).\n", startX, startY);continue;}printf("Please enter the end point (x,y): ");if (scanf("%d,%d", &endX, &endY) != 2) {printf("Error: Invalid input for end point.\n");continue;}if (!isValidPoint(maze, n, m, endX, endY)) {printf("Error: Invalid end point (%d,%d).\n", endX, endY);continue;}// 使用广度优先搜索算法搜索最短路径BFS(maze, n, m, startX, startY, endX, endY);}return 0;
}

maze.txt内容

7 9
1 0 0 0 1 0 1 1 0
0 1 0 1 1 0 0 0 0
0 0 0 0 0 0 1 1 1
1 1 0 1 0 1 0 0 0
0 0 0 1 0 0 0 1 1
1 1 0 0 0 1 0 0 0
0 0 0 1 0 1 0 0 0