Prison Escape

这是codechef starter 134 div4的第六题。
题目链接

题目大意

NxM的01矩阵，0代表罪犯，1代表守卫者。罪犯可以上下左右移动，计算罪犯最少需要经过几个守卫者才能逃出这个矩阵。我们要求出这些罪犯里边经过最少守卫者数量的最大值。
数据范围：T 1000，N和M 3e5，NxM<3e5。

赛时回顾

一眼最短路，但是看见数据范围就没有去写代码。我觉得每个0点去执行最短路算法应该会超时。或者直接每个0进行bfs应该也会超时。

正解

有个东西叫多源最短路。实际上我应该换位思考，不是去求0到边界的最短路，而是边界到0的最短路。多源最短路有两种方法，一是设置虚拟节点连接到所有源，二是直接把所有源节点压入队列中，不需要理会。

所以实际上这个题目是典型的0-1BFS问题。我们只需要将所有边界节点压入队列中，然后一点点向内更新距离即可。最后答案就是d[i][j]。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxlen = 3e5+10;

int main()
{
    int T;
    cin >> T;
    while(T--){
        int n,m;
        cin >> n >> m;
        string a[n];
        for(int i=0;i<n;i++){
            cin >> a[i];
        }
        vector<vector<int> > d(n,vector<int>(m,INT_MAX));
        deque<pair<int,int> > dq;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(i==0||j==0||i==n-1||j==m-1){
                    d[i][j]=a[i][j]-'0';
                    if(d[i][j]==0){
                        dq.push_front({i,j});
                    }
                    else dq.push_back({i,j});
                }
            }
        }
        int dx[] = {0,0,1,-1};
        int dy[] = {1,-1,0,0};
        while(!dq.empty()){
            int x = dq.front().first;
            int y = dq.front().second;
            dq.pop_front();
            for(int i=0;i<4;i++){
                int xx = x+dx[i];
                int yy = y+dy[i];
                if(xx<0||yy<0||xx>=n||yy>=m) continue;

                int weight = a[xx][yy]-'0';
                if(d[x][y]+weight<d[xx][yy]){
                    d[xx][yy]=d[x][y]+weight;
                    if(weight==0){
                        dq.push_front({xx,yy});
                    }
                    else dq.push_back({xx,yy});
                }
            }
        }

        int ans = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(a[i][j]=='0'){
                    ans = max(ans,d[i][j]);
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}