C语言广度优先遍历解迷宫问题并输出线路

以下是使用 C 语言实现广度优先遍历解迷宫问题并输出线路的代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define ROW 5   // 迷宫行数
#define COL 5   // 迷宫列数

typedef struct {
    int row;
    int col;
} Point;        // 表示迷宫中的一个点

typedef struct {
    Point point;
    int step;
} Node;         // 表示 BFS 中的一个节点

Point start = {0, 0};   // 起点
Point end = {4, 4};     // 终点

int maze[ROW][COL] = {   // 迷宫地图，0 表示可通过，1 表示障碍物
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 1, 0, 1, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 1, 0},
};

Point prev[ROW][COL];   // 记录每个节点的前驱节点，用于输出路径

bool visited[ROW][COL]; // 标记每个节点是否被访问过

Node queue[ROW * COL];  // 队列，存储 BFS 中待访问的节点

int front = 0;  // 队列头指针
int rear = 0;   // 队列尾指针

// 判断点是否在迷宫内且可通过
bool isValid(Point point) {
    if (point.row < 0 || point.row >= ROW || point.col < 0 || point.col >= COL)
        return false;
    if (maze[point.row][point.col] == 1)
        return false;
    return true;
}

// BFS 遍历迷宫
void bfs() {
    // 初始化起点
    visited[start.row][start.col] = true;
    queue[rear++] = (Node){start, 0};

    // BFS 遍历
    while (front < rear) {
        Node curr = queue[front++];     // 取出队首节点
        Point currPoint = curr.point;   // 当前节点的位置

        if (currPoint.row == end.row && currPoint.col == end.col) {
            // 找到终点，退出
            return;
        }

        // 遍历当前节点的四个相邻节点
        Point nextPoints[4] = {
            {currPoint.row - 1, currPoint.col},
            {currPoint.row, currPoint.col + 1},
            {currPoint.row + 1, currPoint.col},
            {currPoint.row, currPoint.col - 1},
        };
        for (int i = 0; i < 4; i++) {
            Point nextPoint = nextPoints[i];
            if (isValid(nextPoint) && !visited[nextPoint.row][nextPoint.col]) {
                // 如果相邻节点可通过且未被访问过，加入队列
                visited[nextPoint.row][nextPoint.col] = true;
                queue[rear++] = (Node){nextPoint, curr.step + 1};
                prev[nextPoint.row][nextPoint.col] = currPoint;
            }
        }
    }
}

// 输出路径
void printPath() {
    Point curr = end;
    while (curr.row != start.row || curr.col != start.col) {
        printf("(%d, %d) -> ", curr.row, curr.col);
        curr = prev[curr.row][curr.col];
    }
    printf("(%d, %d)\n", start.row, start.col);
}

int main() {
    bfs();
    printPath();
    return 0;
}

该代码使用 BFS 遍历迷宫，并记录每个节点的前驱节点，用于输出路径。首先定义了 `Point` 和 `Node` 结构体来表示迷宫中的点和 BFS 遍历中的节点，定义了起点和终点、迷宫地图、前驱节点数组和 visited 数组等变量。然后实现了 `isValid()` 函数用于判断一个点是否在迷宫内且可通过，以及 `bfs()` 函数用于 BFS 遍历迷宫。在 `bfs()` 函数中，用队列存储待访问的节点，每次取出队首节点并遍历其四个相邻节点，如果相邻节点可通过且未被访问过，就加入队列，并记录其前驱节点。当找到终点时，就退出 BFS 遍历。最后实现了 `printPath()` 函数用于输出路径。该代码的时间复杂度为 $O(mn)$，其中 $m$ 和 $n$ 分别为迷宫的行数和列数。