题解 | #地牢逃脱#

BFS搜索到各个点的最短距离。
在所有最短距离中取最大值
注意这个不能使用for(int i = 0; i <qx.size(); i++)， 因为qx在过程中能够会减小。
int len = qx.size();
for(int i = 0; i <len; i++){

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

bool isValid(int x, int y, vector<string> &grid){
    if(x < 0 or y < 0 or x >= grid.size() or y >= grid[1].size()) return false;
    else if(grid[x][y] == 'X') return false;
    else return true; 
}

int main(){
    int n, m; cin >> n >> m;
    vector<string> grid(n);
    for(int i = 0; i < n; i ++){
        string s; cin >> s;
        grid[i] = s;
    }
    int startx, starty; cin >> startx >> starty;
    int k; cin >> k;
    vector<vector<int>> steps(k, vector<int>(2, 0));
    for(int i = 0; i < k; i ++){
        int a, b; cin >> a>> b;
        steps[i][0] = a; steps[i][1] = b;
    }
    vector<vector<int>> dist(n, vector<int>(m, 1000));
    queue<int> qx; queue<int> qy;
    int d = 0;
    dist[startx][starty] = d;
    qx.push(startx); qy.push(starty);
    while(!qx.empty()){
        d ++;
        queue<int> tempx; queue<int> tempy;
        int len = qx.size();
        for(int i = 0; i <len; i++){
            // 取出所有可用节点
            int tx = qx.front();qx.pop();
            int ty = qy.front();qy.pop();
            for(int j = 0; j < k; j ++){
                // 便利所有临界点， 只有当距离小于之前的距离时才能加入新的队列
                if(isValid(tx + steps[j][0], ty + steps[j][1], grid)){
                    if(d <= dist[tx + steps[j][0]][ty + steps[j][1]]){
                        tempx.push(tx + steps[j][0]);
                        tempy.push(ty + steps[j][1]);
                        dist[tx + steps[j][0]][ty + steps[j][1]] = d;
                    }
                }
            }
        }
        qx = tempx; qy = tempy;
    }
    int res = 0;
    for(int i  = 0; i < n ; i ++){
        for(int j = 0; j < m; j++){
            if(grid[i][j] == 'X') continue;
            res = max(res, dist[i][j]);
        }
    }
    if(res == 1000) cout << -1 << endl;
    else cout << res << endl;

    return 0;
}