题解 | #走迷宫#

#include<iostream>
#include <queue>
#include<vector>
 // 整体思路是每走一步，计算一步路径数目
using namespace std;

// 参数的输入：x，y均需要做减一操作
void BFS(vector<vector<char>>& graph, int start_x, int start_y, int end_x, int end_y){ 
    int Xstep[4] = {1,0,-1,0};  // 用于实现上下步进
    int Ystep[4] = {0,1,0,-1};  // 用于实现左右步进
    // 计算每一步的最近步数
    vector<vector<int>> StepCouter(size(graph),vector<int>(size(graph[0]),0));
    queue<pair<int,int>> AuxQ;
    AuxQ.push({start_x,start_y});
    
    while(!AuxQ.empty()){
        int sx = AuxQ.front().first;
        int sy = AuxQ.front().second;
        graph[sx][sy] = '*';  // 先自断后路，往前走
        AuxQ.pop();
        for(int i = 0; i < 4; i++){
            int x = sx + Xstep[i]; // 行号，是往上下走
            if(x < 0){ x = 0;}
            int y = sy + Ystep[i]; // 列号，是往左右走 
            if(y < 0){ y = 0;}
            // 除了考虑是否有障碍物，还需判断是否越界
            if(x < size(graph) && y < size(graph[0]) && graph[x][y] != '*'){
                StepCouter[x][y] = StepCouter[sx][sy] + 1;
                graph[x][y] = '*';  // 不走回头路
                AuxQ.push({x,y});
            }
        }
    }
    if(StepCouter[end_x][end_y] != 0){
        cout << StepCouter[end_x][end_y];
    }else {
        cout << -1;
    }
    
}
int main (){
    int Gn = 0, Gm = 0;  // x, y
    cin >> Gn >> Gm;
    int StartX = 0, StartY = 0;
    int EndX = 0, EndY = 0;
    cin >> StartX >> StartY >> EndX >> EndY;
    vector<vector<char>> Graph(Gn, vector<char>(Gm, 0));
    for(int j = 0; j < Gn; j ++){
        for(int k = 0; k < Gm; k++){
            cin >> Graph[j][k];
        }
    }
    if(Graph[EndX-1][EndY-1] == '*'){
        cout << -1;
        return 0;
    }
    BFS(Graph, StartX-1, StartY-1, EndX-1, EndY-1);
    return 0;
}