题解 | 迷宫寻路

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

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]);

    int vis[105][105] = { 0 };
    int front = 0, rear = 0;
    int qx[105*105], qy[105*105];

    qx[rear] = 0;   //初始化首个x坐标
    qy[rear] = 0;   //初始化首个y坐标
    rear++;         //向后移动末尾指针
    vis[0][0] = 1;  //标记首坐标已被使用
    //用来对当前坐标进行上下左右四向搜索
    int dx[4] = {-1,  0, 0, 1};
    int dy[4] = { 0, -1, 1, 0};

    while(front < rear){
        int x = qx[front];
        int y = qy[front];
        front++;

        if(x == n-1 && y == m-1){
            printf("Yes\n");
            return 0;
        }
        for(int i = 0; i < 4; i++){
            int cur_x = x + dx[i];
            int cur_y = y + dy[i];
            if(cur_x >= 0 && cur_x < n && cur_y >= 0 && cur_y < m){
                if(ch[cur_x][cur_y] == '.' && !vis[cur_x][cur_y]){
                    vis[cur_x][cur_y] = 1;  //标记走过
                    qx[rear] = cur_x;
                    qy[rear] = cur_y;
                    rear++;
                }
            }
        }
    }
    printf("No\n");
    return 0;
}