热门标签
热门文章
- 1【汽车电子】浅谈车载系统QNX_车机qnx虚拟化软件系统架构
- 2STM32烧写hex及bin文件的五种方法_keil直接烧写bin文件
- 3java 暂停_Java多线程程序休眠、暂停与停止
- 4探索安全边界：解锁Android应用的HTTPS流量检验——android-ssl-pinning-bypass工具评测
- 5Kali Linux漏洞评估与渗透测试_kali网站漏洞扫描
- 6爬虫系统
- 7MIXLAB NODE熊叔的故事#AI如何改变产品经理的工作
- 8详细讲解 Keil Pack Installer，以及通过 Keil 官网获取 Pack
- 9大模型和数据要素赋能能源化工行业数字化转型建设和实施方案_化工行业的数据资源
- 10【芳心科技】B. 无线陀螺仪设定轨迹行走小车_芳心科技mpu小车
当前位置: article > 正文
广度优先搜索算法 - 迷宫找路_广度优先算法迷宫
作者：小惠珠哦 | 2024-08-23 04:22:09
赞
踩
广度优先算法迷宫
这是一个提问者的提出的问题： 连接
数据结构算法，用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 100 typedef 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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
2.2 源码解释
#define _CRT_SECURE_NO_WARNINGS
- 1
我的编译器使用的是vs2017，而我在代码中使用了fopen等函数，编译器认为：使用的是不安全的C标准库函数fopen()，建议使用更安全的fopen_s()函数来代替。但是没有必要，所以我加上了这行代码，让编译器忽略这个警告。如果你的编译器运行我之前的代码，编译没有报错，你也可以将这一行去掉。
int startX = 0,startY = 0, endX = n - 1, endY = m - 1;
- 1
这一行是在main函数中的，他的目的就是确定迷宫的入口和出口，默认是左上到右下，你可以通过更改数值实现，自定义入口和出口。
例如：起点（0,1）；终点（6，8）
int startX = 0,startY = 1, endX = 6, endY = 7;
- 1
这里我提供一个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
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
你可能注意到了，我的迷宫结构和之前提供给你的迷宫结构发生了变化，在开始处，增加了迷宫的大小“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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
然后，在 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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
这样做的好处是，将读取迷宫数据的代码封装成一个函数，可以使 main 函数更加清晰简洁，也方便在其他函数中重复使用该代码。另外，添加判断文件是否成功打开的代码，可以在打开文件失败时及时提示用户，并退出程序。
3.2 增加错误处理
- 判断自定义的迷宫入口和出口是否合法，比如说，刚才迷宫大小为7*9，你却定义一个出口为（10,11），那么这个出口肯定是越界了
- 以及判断你自定义迷宫入口和出口是否合法，也就是说，如果你设计迷宫入口或者出口为“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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
然后，我们可以在 BFS 函数和 main 函数中使用该函数来检查起点和终点的合法性。例如，在 BFS 函数中，可以将下面这行代码：
if (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] == 0 && !visited[nx][ny]) {
- 1
修改为：
if (isValidPoint(maze, n, m, nx, ny) && !visited[nx][ny]) {
- 1
在 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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
这样，当输入的起点或终点不合法时，程序会输出错误信息并退出。
我们使用刚才的迷宫进行测试，起点设置为（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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
运行结果：
5 完整代码
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX_SIZE 100 typedef 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; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
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
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小惠珠哦/article/detail/1019442
推荐阅读
相关标签
