题解 | #走迷宫#

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
typedef  pair<int,int> pnt;
struct point{
    int x;
    int y;
};
int main() {
    // 定义迷宫长宽
    int n, m;
    cin >> n;
    cin >> m;
    // 输入重点和起点坐标
    point ps,pt;
    cin >> ps.x;
    cin >> ps.y;
    cin >> pt.x;
    cin >> pt.y;
    // 初始化迷宫矩阵 0表示障碍 1表示可通行 2表示已经访问过
    vector<vector<int>> vect(n + 2, vector<int>(m + 2, 0));
    // 访问数组 默认-1未访问 同时走过距离也用这个矩阵统计
    vector<vector<int>> visit(n + 2, vector<int>(m + 2, -1));
    // st用于暂存上一次访问的节点，以便回退
    queue<pnt> st;
    // 循环输入数据
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char ch;
            cin >> ch;
            if (ch == '.') vect[i][j] = 1;
        }
    }
    st.push({ps.x,ps.y});
    visit[ps.x][ps.y]=0;
    // 如果终点不通直接输出-1 结束
    if (vect[pt.x][pt.y] == 0) {
        cout << -1 << endl;
        return 0;
    }
    // 出栈条件 只有到达目标顶点或者栈空(无路可走) 退出循环
    while ((ps.x != pt.x || ps.y != pt.y) && !st.empty()) {
        // 出栈一点
        auto p=st.front();
        ps.x=p.first;ps.y=p.second;
        st.pop();
        // 出栈进行访问 用ps接受当前
       int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
       for(int i=0;i<4;i++){
           //取下一个点
           point ptemp;
           ptemp.x=ps.x+dx[i];ptemp.y=ps.y+dy[i];
           // 判断是否可通行且该点未访问过
           if(vect[ptemp.x][ptemp.y]==1&&visit[ptemp.x][ptemp.y]==-1){
              st.push({ptemp.x,ptemp.y});
              visit[ptemp.x][ptemp.y]=visit[ps.x][ps.y]+1;
              if(ps.x == pt.x && ps.y == pt.y) break;
           }
       }
    }
    if(ps.x == pt.x && ps.y == pt.y) cout<<visit[pt.x][pt.y]<<endl;
    else cout<<-1<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")