迷宫问题c语言广度优先

广度优先遍历是一种基于队列的搜索算法，适用于求解最短路径或最小步数等问题。下面是使用广度优先遍历求解迷宫问题的C语言代码：

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

#define ROW 5
#define COL 5

typedef struct {
    int row;  // 行坐标
    int col;  // 列坐标
} Point;

int maze[ROW][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}
};  // 迷宫，0代表可走，1代表障碍

int visited[ROW][COL] = {0};  // 记录是否已经访问过

int BFS(Point start, Point end);

int main() {
    Point start = {0, 0};  // 起点
    Point end = {ROW-1, COL-1};  // 终点
    int steps = BFS(start, end);
    printf("从起点到终点的最短步数为：%d\n", steps);
    return 0;
}

int BFS(Point start, Point end) {
    Point queue[ROW*COL];  // 队列（使用数组模拟）
    int front = 0, rear = 0;  // 队头和队尾
    queue[rear++] = start;  // 入队
    visited[start.row][start.col] = 1;  // 标记为已访问
    int steps = 0;  // 步数
    while (front < rear) {  // 队列非空
        int size = rear - front;  // 当前层的节点数
        while (size-- > 0) {  // 处理当前层的所有节点
            Point cur = queue[front++];  // 出队
            if (cur.row == end.row && cur.col == end.col) {  // 到达终点
                return steps;
            }
            // 向上走
            if (cur.row > 0 && maze[cur.row-1][cur.col] == 0 && visited[cur.row-1][cur.col] == 0) {
                Point next = {cur.row-1, cur.col};
                queue[rear++] = next;  // 入队
                visited[next.row][next.col] = 1;  // 标记为已访问
            }
            // 向下走
            if (cur.row < ROW-1 && maze[cur.row+1][cur.col] == 0 && visited[cur.row+1][cur.col] == 0) {
                Point next = {cur.row+1, cur.col};
                queue[rear++] = next;  // 入队
                visited[next.row][next.col] = 1;  // 标记为已访问
            }
            // 向左走
            if (cur.col > 0 && maze[cur.row][cur.col-1] == 0 && visited[cur.row][cur.col-1] == 0) {
                Point next = {cur.row, cur.col-1};
                queue[rear++] = next;  // 入队
                visited[next.row][next.col] = 1;  // 标记为已访问
            }
            // 向右走
            if (cur.col < COL-1 && maze[cur.row][cur.col+1] == 0 && visited[cur.row][cur.col+1] == 0) {
                Point next = {cur.row, cur.col+1};
                queue[rear++] = next;  // 入队
                visited[next.row][next.col] = 1;  // 标记为已访问
            }
        }
        steps++;  // 层数加1
    }
    return -1;  // 无解的情况
}

以上代码中，定义了一个`Point`结构体表示坐标，使用了两个二维数组`maze`和`visited`分别表示迷宫和是否已访问。在`BFS()`函数中，使用队列依次处理每一层的节点，直到到达终点或队列为空。在处理每个节点时，检查其上下左右四个方向是否可走，若可走则将其入队并标记为已访问。主函数中调用`BFS()`函数并输出最短步数。