题解 | #走迷宫#

/*
笨方法，仍然用bfs,每次遍历4个方向上的点
*/
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> s(n, vector<int>(m));  // 初始化大小为n行m列的二维向量
    vector<vector<int>> dist(n, vector<int>(m, -1));  // 初始化大小为n行m列，默认值为-1的二维向量

    int xs, ys, xt, yt;
    char point;

    cin >> xs >> ys >> xt >> yt;
    --xs,--ys,--xt,--yt;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> point;
            if (point == '*') s[i][j] = 1;
            if (point == '.') s[i][j] = 0;
        }
    }
    dist[xs][ys] = 0;
    queue<pair<int,int>> pos;
    pos.push({xs,ys});
    bool ans = false;
    while(!pos.empty()){
        vector<pair<int,int>> chosens;
        auto from = pos.front();
        pos.pop();
        int x_from = from.first, y_from = from.second;
    
        //cout<<x_from<<" "<<y_from<<endl;
        int x_to,y_to;
        //上
        if((y_from-1>=0)&&(s[x_from][y_from-1]!=1)){
            x_to = x_from;
            y_to = y_from-1;
            chosens.push_back({x_to,y_to});
        }
        //下
        if((y_from+1<m)&&(s[x_from][y_from+1]!=1)){
            x_to = x_from;
            y_to = y_from+1;
            chosens.push_back({x_to,y_to});
        }
        //右       
        if((x_from+1<n)&&(s[x_from+1][y_from]!=1)){
            x_to = x_from+1;
            y_to = y_from;
            chosens.push_back({x_to,y_to});
        }
        //左
        if((x_from-1>=0)&&(s[x_from-1][y_from]!=1)){
            x_to = x_from-1;
            y_to = y_from;
            chosens.push_back({x_to,y_to});
        } 
        for(auto chose:chosens){
            x_to = chose.first;
            y_to = chose.second;
            if(dist[x_to][y_to]==-1){
                dist[x_to][y_to] = dist[x_from][y_from] + 1;
                if(x_to==xt&&y_to==yt){
                    ans = true;
                    break;
                }
                pos.push({x_to,y_to});
            }
        }
        if(ans==true)break;
    }
    cout<<dist[xt][yt];
    return 0;
}
// 64 位输出请用 printf("%lld")