题解 | #走迷宫#

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

const int N = 1010;
char mpt[N][N];
int vis[N][N];
int dir[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int h, w;
int sx, sy, ex, ey;

struct Node {
    int x, y, dist;
};

int bfs() {
    queue<Node> q;
    q.push({sx, sy, 0});
    vis[sx][sy] = 1;

    while (!q.empty()) {
        Node now = q.front();
        q.pop();

        if (now.x == ex && now.y == ey) {
            return now.dist;
        }

        for (int i = 0; i < 4; i++) {
            int nx = now.x + dir[i][0];
            int ny = now.y + dir[i][1];
            if (nx > 0 && nx <= h && ny > 0 && ny <= w && vis[nx][ny]==0 && mpt[nx][ny] == '.') {
                vis[nx][ny] = 1;
                q.push({nx, ny, now.dist + 1});
            }
        }
    }

    return -1; // 如果队列清空还没有找到，返回-1
}

int main() {
    cin >> h >> w;
    cin >> sx >> sy >> ex >> ey;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> mpt[i][j];
        }
    }

    memset(vis, 0, sizeof(vis));
    int ans = bfs();
    cout << ans << endl;
    return 0;
}