c语言用bfs算法求解迷宫,将所有路径求出,并列出最短路径,若最短路径有很多,需要将所有最短路径都列出
时间: 2024-01-30 19:01:29 浏览: 31
好的,这是一个关于 C 语言使用 BFS 算法求解迷宫的问题。
首先,BFS 算法可以用来搜索迷宫中的所有路径,并且可以找到最短路径。具体实现步骤如下:
1. 定义一个数组用来表示迷宫,1 表示障碍物,0 表示可以通过。
2. 定义一个队列,用来存储待搜索的节点。
3. 定义一个数组用来记录每个节点是否已经被访问过。
4. 从起点开始,将其加入队列,并将其标记为已访问。
5. 不断从队列中取出节点,将其相邻的未访问节点加入队列,并标记为已访问。
6. 如果找到终点,记录下路径并更新最短路径。
7. 循环以上步骤直到队列为空。
以下是一份 C 语言代码,可以实现上述算法:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 定义迷宫,1 表示障碍物,0 表示可以通过
int maze[5][5] = {
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 1, 0}
};
// 定义节点结构体
typedef struct {
int x;
int y;
int step;
int parent;
} node;
// 定义队列结构体
typedef struct {
node *data;
int head;
int tail;
int size;
} queue;
// 初始化队列
queue* init_queue(int size) {
queue *q = (queue*)malloc(sizeof(queue));
q->data = (node*)malloc(sizeof(node) * size);
q->head = 0;
q->tail = 0;
q->size = size;
return q;
}
// 入队
bool enqueue(queue *q, node n) {
if ((q->tail + 1) % q->size == q->head) {
return false;
}
q->data[q->tail] = n;
q->tail = (q->tail + 1) % q->size;
return true;
}
// 出队
node dequeue(queue *q) {
node n = q->data[q->head];
q->head = (q->head + 1) % q->size;
return n;
}
// 判断节点是否合法
bool is_valid_node(int x, int y) {
if (x < 0 || x >= 5 || y < 0 || y >= 5) {
return false;
}
if (maze[x][y] == 1) {
return false;
}
return true;
}
// BFS 搜索迷宫
void bfs() {
// 定义起点和终点
node start = {0, 0, 0, -1};
node end = {4, 3, -1, -1};
// 定义队列,并将起点入队
queue *q = init_queue(100);
enqueue(q, start);
// 定义数组记录每个节点是否已经访问过
bool visited[5][5] = {false};
// 定义数组记录每个节点的父节点
int parent[25] = {-1};
// 定义最短路径长度
int min_step = -1;
// 定义变量记录搜索节点的数量
int count = 0;
// 循环搜索
while (q->head != q->tail) {
// 取出队列中的一个节点
node n = dequeue(q);
count++;
// 如果该节点为终点,记录路径并更新最短路径长度
if (n.x == end.x && n.y == end.y) {
if (min_step == -1 || n.step < min_step) {
min_step = n.step;
}
parent[n.x * 5 + n.y] = n.parent;
continue;
}
// 遍历该节点的相邻节点
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
for (int i = 0; i < 4; i++) {
int nx = n.x + dx[i];
int ny = n.y + dy[i];
if (is_valid_node(nx, ny) && !visited[nx][ny]) {
visited[nx][ny] = true;
node nn = {nx, ny, n.step + 1, n.x * 5 + n.y};
enqueue(q, nn);
parent[nx * 5 + ny] = n.x * 5 + n.y;
}
}
}
// 如果没有找到终点,输出无解
if (min_step == -1) {
printf("No solution.\n");
return;
}
// 输出最短路径长度
printf("Min step: %d\n", min_step);
// 定义数组记录最短路径
int path[25] = {-1};
// 从终点开始回溯路径
int curr = end.x * 5 + end.y;
int i = 0;
while (curr != -1) {
path[i++] = curr;
curr = parent[curr];
}
// 输出所有最短路径
printf("All shortest paths:\n");
for (int j = i - 2; j >= 0; j--) {
printf("(%d, %d) -> ", path[j] / 5, path[j] % 5);
}
printf("(%d, %d)\n", end.x, end.y);
// 输出搜索节点数量
printf("Search nodes: %d\n", count);
}
int main() {
bfs();
return 0;
}
```
这份代码可以输出最短路径长度以及所有最短路径,并且还可以统计搜索节点的数量。如果最短路径有多条,会将所有最短路径都输出。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)