题解 | 走迷宫

#include <iostream>
#include <queue>
#include <map>

using namespace std;

int main() {
    //输入数据
    int n, m;
    cin >> n >> m;
    int xs, ys, xt, yt;
    cin >> xs >> ys >> xt >> yt;
    char g[n][m];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> g[i][j];
        }
    }
    //辅助数组
    int x[4] = {-1, 1, 0, 0};
    int y[4] = {0, 0, -1, 1};
    //bfs搜索找出最短距离，队列q存储节点，.改为，标记为访问,dist标记距离起始点距离
    queue<pair<int, int>> q;//bfs队列
    map<pair<int, int>, int> dist;
    pair<int, int> end = {xt - 1, yt - 1};//终点坐标
    //起点入队列，标记访问，记录距离为0
    q.push({xs - 1, ys - 1});
    g[xs][ys] = ',';
    dist[{xs - 1, ys - 1}] = 0;
    while(!q.empty()){
        //出队列结点
        pair<int, int> current = q.front();
        q.pop();
        if(current == end){
            break;//找到到达终点的路径
        }
        int xc = current.first;
        int yc = current.second;
        //访问邻接结点
        for(int k = 0; k < 4; k++){
            int xi = xc + x[k];
            int yi = yc + y[k];
            //满足条件的未访问点
            if(xi >= 0 && xi < n && yi >= 0 && yi < m && g[xi][yi] == '.'){
                q.push({xi, yi});
                g[xi][yi] = ',';
                dist[{xi, yi}] = dist[current] + 1;
            }
        }
    }

    //输出结果
    if(dist.count(end)){
        cout << dist[end] << endl;
    }
    else{
        cout << -1 << endl;
    }

    return 0;
}
// 64 位输出请用 printf("%lld")