用队列求解迷宫问题C语言

在C语言中，使用队列（Queue）解决迷宫问题通常涉及到广度优先搜索（Breadth-First Search, BFS）。以下是基本步骤：

1. 定义结构体表示节点，包含当前位置和访问状态（比如标记为起点、已访问或无法到达）。
2. 创建两个队列，一个用于存储起始位置（起点），另一个用于存放后续的移动路径。
3. 将起点入队，并设置其为已访问状态。
4. 当队列非空时，执行循环：
a. 弹出队首元素，检查当前节点是否是终点，如果是，则结束搜索并返回路径。
b. 如果当前节点不是终点，查看其周围四个相邻的节点（上、下、左、右），如果它们是未访问并且在迷宫范围内，将它们加入队列，并更新为已访问状态。
5. 如果遍历完所有可达节点仍找不到终点，说明迷宫无解。

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

typedef struct Node {
    int x, y; // 节点坐标
    char visited; // 访问状态
} Node;

Node* maze_bfs(int maze[][maze_size], int start_x, int start_y, int end_x, int end_y) {
    Node queue[queue_capacity];
    int front = -1, rear = 0;
    
    queue[rear++] = (Node){start_x, start_y, 1}; // 初始化，1表示已访问

    while(front != rear) {
        Node current = queue[front++];
        if(current.x == end_x && current.y == end_y)
            return &current; // 找到终点

        if(maze[current.x][current.y] == 0) { // 非墙壁
            if(current.x > 0 && maze[current.x - 1][current.y] == 1) {
                queue[rear++] = (Node){current.x - 1, current.y, 1};
            }
            if(current.x < maze_size - 1 && maze[current.x + 1][current.y] == 1) {
                queue[rear++] = (Node){current.x + 1, current.y, 1};
            }
            if(current.y > 0 && maze[current.x][current.y - 1] == 1) {
                queue[rear++] = (Node){current.x, current.y - 1, 1};
            }
            if(current.y < maze_size - 1 && maze[current.x][current.y + 1] == 1) {
                queue[rear++] = (Node){current.x, current.y + 1, 1};
            }
        }
    }

    return NULL; // 迷宫无解
}

int main() {
    // ... 初始化迷宫矩阵，开始和结束坐标 ...
    Node* path = maze_bfs(maze, start_x, start_y, end_x, end_y);
    if(path)
        print_path(path);
    else
        printf("No solution.\n");
    return 0;
}