迷宫问题c语言广度优先

广度优先搜索（BFS）常用于解决迷宫问题。下面是一个简单的迷宫问题的C语言实现：

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

#define ROW 5
#define COL 5

struct Node{
    int x;
    int y;
    int step;
    int prev;
};

int bfs(int maze[ROW][COL], int start_x, int start_y, int end_x, int end_y){
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    int visited[ROW][COL] = {0};
    struct Node queue[ROW * COL];
    int head = 0, tail = 0;
    queue[tail].x = start_x;
    queue[tail].y = start_y;
    queue[tail].step = 0;
    queue[tail].prev = -1;
    tail++;
    visited[start_x][start_y] = 1;
    while(head < tail){
        struct Node cur = queue[head];
        head++;
        if(cur.x == end_x && cur.y == end_y){
            printf("The shortest path is %d.\n", cur.step);
            int prev = cur.prev;
            while(prev != -1){
                printf("(%d, %d) <- ", queue[prev].x, queue[prev].y);
                prev = queue[prev].prev;
            }
            printf("(%d, %d)\n", cur.x, cur.y);
            return cur.step;
        }
        for(int i = 0; i < 4; i++){
            int next_x = cur.x + dx[i];
            int next_y = cur.y + dy[i];
            if(next_x >= 0 && next_x < ROW && next_y >= 0 && next_y < COL && maze[next_x][next_y] == 0 && visited[next_x][next_y] == 0){
                visited[next_x][next_y] = 1;
                queue[tail].x = next_x;
                queue[tail].y = next_y;
                queue[tail].step = cur.step + 1;
                queue[tail].prev = head - 1;
                tail++;
            }
        }
    }
    printf("There is no path from (%d, %d) to (%d, %d).\n", start_x, start_y, end_x, end_y);
    return -1;
}

int main(){
    int maze[ROW][COL] = {
        {0, 0, 0, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 0, 0, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 0, 0, 0, 0}
    };
    bfs(maze, 0, 0, 4, 4);
    return 0;
}

在这个例子中，我们使用了一个结构体`Node`来表示迷宫中的一个节点，其中`x`和`y`表示节点的坐标，`step`表示从起点到当前节点的步数，`prev`表示当前节点的前一个节点在队列中的下标。

在`bfs`函数中，我们使用了一个队列来进行广度优先搜索。首先将起点加入队列中，并标记为已经访问过。然后不断从队列头部取出节点，对其四个相邻节点进行判断，如果满足条件则加入队列，并标记为已经访问过。重复以上过程，直到队列为空或者找到终点。

当找到终点时，我们可以根据节点的`prev`属性回溯到起点，输出最短路径。