题解 | 迷宫寻路

#include <stdio.h>
#include <stdlib.h>
//坐标
typedef struct {
    int x, y;
}Point;
//队头尾
typedef struct {
    Point data[105 * 105];
    int front, rear;
}Queue;
//初始化队头尾函数
void initQueue(Queue* q) {
    q->front = 0;   //头部
    q->rear = 0;    //尾部
}
//检测是否为空
int isQueueEmpty(Queue* q) {
    return q->front == q->rear;
}
//载入队列函数
void enqueue(Queue* q, int x, int y) {
    q->data[q->rear].x = x;
    q->data[q->rear].y = y;
    q->rear++;
}
//载出队列函数
Point dequeue(Queue* q) {
    return q->data[q->front++];
}
int main(void) {
    int n, m;
    scanf("%d%d", &n, &m);

    char ch[105][105];  //网格
    for (int i = 0; i < n; i++)
        scanf("%s", ch[i]);

    if (ch[0][0] == '#' || ch[n - 1][m - 1] == '#') {
        printf("No\n");
        return 0;
    }
    //初始化队列
    Queue q;
    initQueue(&q);
    //访问并标记
    int visited[105][105] = { 0 };  //访问标记的数组
    enqueue(&q, 0, 0);
    visited[0][0] = 1;
    //四向搜索
    int dx[4] = { -1, 1, 0, 0 };   //左-1右+1
    int dy[4] = { 0, 0, -1, 1 };   //上-1下+1
    //BFS搜索
    while (!isQueueEmpty(&q)) {
        //取出队首的数
        Point current = dequeue(&q);
        int x = current.x;
        int y = current.y;
        //能到达出口
        if (x == n - 1 && y == m - 1) {
            printf("Yes\n");
            return 0;
        }
        //四向寻找
        for (int i = 0; i < 4; i++) {
            int cx = x + dx[i];
            int cy = y + dy[i];
            //确保在网格内
            if (cx >= 0 && cx < n && cy >= 0 && cy < m) {
                //是通路且未被访问
                if (ch[cx][cy] == '.' && !visited[cx][cy]) {
                    visited[cx][cy] = 1;
                    enqueue(&q, cx, cy);
                }
            }
        }
    }
    printf("No\n");
    return 0;
}