题解 | 走迷宫

#include <stdio.h>
#include <string.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 };
    memset(vis, 0, sizeof(vis));
    memset(dis, 0, sizeof(dis));

    int front = 0, rear = 0;
    int qx[1005 * 1005], qy[1005 * 1005];
    qx[rear] = sx;
    qy[rear] = sy;
    rear++;
    vis[sx][sy] = 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;
}