题解 | 走迷宫

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

struct Point {
    int x, y;
};

int main() {
    int n, m;
    cin >> n >> m;
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    // 转换为0-indexed
    sx--; sy--; tx--; ty--;
    
    vector<string> grid(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    
    // 距离数组，初始化为-1表示未访问
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<Point> q;
    dist[sx][sy] = 0;
    q.push({sx, sy});
    
    // 四个方向：上、下、左、右
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    
    while (!q.empty()) {
        Point p = q.front();
        q.pop();
        // 到达终点，提前结束BFS
        if (p.x == tx && p.y == ty) {
            break;
        }
        for (int i = 0; i < 4; i++) {
            int nx = p.x + dx[i];
            int ny = p.y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == '.' && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[p.x][p.y] + 1;
                q.push({nx, ny});
            }
        }
    }
    
    cout << dist[tx][ty] << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

障碍物不可通行和到达，初始-1,4个方向广度搜索