题解 | 走迷宫

#include<bits/stdc++.h>

using namespace std;

using ll = long long; // 博主能力有限，如有错误欢迎指正

int dx[] ={-1,0,0,1}; // a s w d 每一次走的位置 **** 可以思考为什么这样
int dy[] ={0 ,1,-1,0};
void bfs(vector<vector<int>> &an ,const int x_s,const int y_s,const int x_t,const int y_t,const int n,const int m){
    deque<pair<pair<int,int>,int>> q;  // 保存要走的位置
    pair<pair<int,int>,int> pos , pos1;
    pos = {{x_s,y_s},0}; // 第一个是当前位置 ， 第二个是 离原点的距离
    q.push_back(pos);
    an[x_s][y_s] = -1;
    while(!q.empty()){ // 如果走不了 结束
    pos1 = q.front();
    int x = pos1.first.first, y = pos1.first.second;
    
    if(x == x_t && y == y_t){ // 到达
        cout << pos1.second; 
        return ;
    }
    for(int i=0;i<4;i++){
        int x_ = x + dx[i] , y_ = y+ dy[i];
        if(x_ <1 || x_ > n || y_ < 1|| y_ > m) continue; // 出界
        if(an[x_][y_] == -1)continue; // 走过
        if(an[x_][y_] == 1)continue; // 障碍
        q.push_back({{x+dx[i],y+dy[i]},pos1.second+1});
        an[x_][y_] = -1;
    }
    q.pop_front();
    }
    cout << -1;
    return;
}

int main(){
    int n , m,x_s , y_s , x_t ,y_t ;
    cin >> n >> m >> x_s >> y_s >> x_t >> y_t;
    vector<vector<int>> an(n+5,vector<int>(m+5,0));
    char c;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> c;
            if(c == '*'){
                an[i][j] = 1; 
            }
        }
    }
    bfs(an,x_s,y_s,x_t,y_t,n,m);
    return 0;
}
// 64 位输出请用 printf("%lld")