题解 | 走迷宫

#include <stdio.h>
#include <string.h>

int main(void) {
    int n, m;
    scanf("%d%d", &n, &m);

    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    x1--, x2--, y1--, y2--;

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

    int vis[1005][1005] = { 0 };
    int dis[1005][1005] = { 0 };
    int front = 0, rear = 0;
    int qx[1005*1005], qy[1005*1005];
    qx[rear] =x1, qy[rear] = y1;
    rear++;
    vis[x1][y1] = 1;
    dis[x1][y1] = 0;

    int dx[4] = {-1, 0, 1,  0};
    int dy[4] = { 0, 1, 0, -1};
    while(front < rear){
        int x = qx[front];
        int y = qy[front];
        front++;
        if(x == x2 && y == y2){
            printf("%d", dis[x][y]);
            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;
                    dis[cur_x][cur_y] = dis[x][y] + 1;
                    qx[rear] = cur_x;
                    qy[rear] = cur_y;
                    rear++;
                }
            }
        }
    }
    printf("-1\n");
    return 0;
}