题解 | 走迷宫

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    
    vector<vector<char>>arr(n+1,vector<char>(m+1)); 
    vector<vector<int>>step(n+1,vector<int>(m+1,-1)); 
    step[x1][y1]=0;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>arr[i][j];
        }
    }
    queue<pair<int,int>>q;
    q.push({x1,y1});
    while(!q.empty()){
        auto it=q.front();
        q.pop();
        
        int i=it.first;
        int j=it.second;
        
        if(i==x2&&j==y2){
            cout<<step[i][j]<<endl;
            return 0;
        }
        int dirs[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
        for(auto &dir:dirs){
            int ni=i+dir[0];
            int nj=j+dir[1];
            if(ni>=1&&ni<=n&&nj>=1&&nj<=m&&step[ni][nj]==-1&& arr[ni][nj] == '.'){
                step[ni][nj]=step[i][j]+1;
                q.push({ni,nj});
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}