企业 办公 网站模板,羊 东莞网站开发,FLASK做wiki网站,洛阳孟津网站建设广度优先搜索算法1 思考问题1.1 这个迷宫需不需要指定入口和出口#xff1f;2 先粗略实现2.1 源码2.2 源码解释3 优化代码3.1 优化读取文件部分3.2 增加错误处理4 再优化-让程序变得更加灵活4.1 用户外部可以循环输入入口和出口5 完整代码这是一个提问者的提出的问题#xff…
广度优先搜索算法1 思考问题1.1 这个迷宫需不需要指定入口和出口2 先粗略实现2.1 源码2.2 源码解释3 优化代码3.1 优化读取文件部分3.2 增加错误处理4 再优化-让程序变得更加灵活4.1 用户外部可以循环输入入口和出口5 完整代码这是一个提问者的提出的问题
连接数据结构算法用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终点68
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 增加错误处理
判断自定义的迷宫入口和出口是否合法比如说刚才迷宫大小为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;
}然后我们可以在 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
