题解 | 走迷宫

#include <stdio.h>

int main(void) {
    int n, m;
    scanf("%d%d", &n, &m);
    int sx, sy, ex, ey;
    scanf("%d%d%d%d", &sx, &sy, &ex, &ey);

    sx--, sy--, ex--, ey--;
    char g[1005][1005];
    for(int i = 0; i < n; i++)
        scanf("%s", &g[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] = sx;
    qy[rear] = sy;
    rear++;
    vis[0][0] = 1;
    dis[sx][sy] = 0;

    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 == ex && y == ey){
            printf("%d\n", 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(g[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;
}