1036. 逃离大迷宫

1036. 逃离大迷宫

得能意识到最优围堵的方法是下图。最优的围堵方法也就是使得我们需要搜索最多位置的方法。

image.png

const int N = 1e6;
class Solution {
public:
    int bfs(set<pair<int,int>>& bs, vector<int>& source, vector<int>& target) {
        int n = bs.size();
        set<pair<int,int>>S;
        queue<pair<int,int>>Q;
        Q.push({source[0], source[1]});
        S.insert({source[0], source[1]});
        int dx[]={-1,0,1,0}, dy[]={0,1,0,-1};
        while(Q.size()) {
            auto u=Q.front();
            Q.pop();
            if(u.first==target[0] && u.second==target[1])return 0;
            for(int i=0;i<4;i++){
                int a=u.first+dx[i], b=u.second+dy[i];
                if(a>=0 && a<N && b>=0 && b<N && bs.count({a,b})==0 && S.count({a,b})==0){
                    S.insert({a,b});
                    if(a==target[0] && b==target[1])return 0;
                    if(S.size()>n*(n-1)/2)return 2;
                    Q.push({a,b});
                }
            }
        }
        if(S.size()<=n*(n-1)/2) return 1;
        return -1;
        // 0: 搜到了，1: 被block，2: 无block
    }
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        set<pair<int,int>>bs;
        for(auto p:blocked)bs.insert({p[0], p[1]});
        int res1=bfs(bs,source,target);
        if(res1==0)return true;
        else if(res1==1)return false;
        int res2=bfs(bs,target,source);
        if(res2==2)return true;
        return false;
    }
};