bfs算法c语言求解迷宫

好的，下面是基于 BFS 算法实现迷宫求解的 C 语言代码：

#include <stdio.h>
#include <stdlib.h>
#define MAX_ROW 5
#define MAX_COL 5

struct Point {
    int row, col;
} queue[MAX_ROW * MAX_COL];

int maze[MAX_ROW][MAX_COL] = {
    {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},
};
int visited[MAX_ROW][MAX_COL];

int front = 0, rear = 0;

void enqueue(struct Point p)
{
    queue[rear++] = p;
}

struct Point dequeue()
{
    return queue[front++];
}

int is_empty()
{
    return front == rear;
}

int bfs()
{
    struct Point p = {0, 0};
    maze[p.row][p.col] = 2;
    visited[p.row][p.col] = 1;
    enqueue(p);

    while (!is_empty()) {
        struct Point current = dequeue();
        if (current.row == MAX_ROW - 1 && current.col == MAX_COL - 1) {
            return 1;
        }
        if (current.col+1 < MAX_COL && maze[current.row][current.col+1] == 0 && !visited[current.row][current.col+1]) {
            struct Point next = {current.row, current.col+1};
            maze[next.row][next.col] = 2;
            visited[next.row][next.col] = 1;
            enqueue(next);
        }
        if (current.row+1 < MAX_ROW && maze[current.row+1][current.col] == 0 && !visited[current.row+1][current.col]) {
            struct Point next = {current.row+1, current.col};
            maze[next.row][next.col] = 2;
            visited[next.row][next.col] = 1;
            enqueue(next);
        }
        if (current.col-1 >= 0 && maze[current.row][current.col-1] == 0 && !visited[current.row][current.col-1]) {
            struct Point next = {current.row, current.col-1};
            maze[next.row][next.col] = 2;
            visited[next.row][next.col] = 1;
            enqueue(next);
        }
        if (current.row-1 >= 0 && maze[current.row-1][current.col] == 0 && !visited[current.row-1][current.col]) {
            struct Point next = {current.row-1, current.col};
            maze[next.row][next.col] = 2;
            visited[next.row][next.col] = 1;
            enqueue(next);
        }
    }
    return 0;
}

void print_maze()
{
    int i, j;
    printf("Maze:\n");
    for (i = 0; i < MAX_ROW; i++) {
        for (j = 0; j < MAX_COL; j++) {
            printf("%d ", maze[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

int main()
{
    if (bfs()) {
        printf("Path found!\n");
    } else {
        printf("Path not found!\n");
    }
    print_maze();
    return 0;
}

这段代码中，我们使用了一个结构体 `Point` 来表示坐标，使用一个数组 `queue` 来实现队列，使用 `visited` 数组来记录已经访问过的位置。

在 `bfs` 函数中，我们首先将起点入队，并将其标记为已访问过。然后在一个循环中，不断从队列中取出元素，分别向四个方向扩展，如果扩展出了终点，就返回 1 表示找到了路径。如果队列为空，说明已经搜索完所有可达的位置，但是没有找到终点，返回 0 表示没有路径。

注意，在扩展一个位置时，需要判断扩展后的位置是否越界、是否是障碍物、是否已经访问过。如果符合要求，将其入队，并将其标记为已访问过，同时在地图上标记为已访问过的位置。

最后，我们输出地图的状态，可以看到所有已访问过的位置都被标记为 2，起点和终点的位置分别为 2 和 0。如果找到了路径，输出 "Path found!"，否则输出 "Path not found!"。