leetcode-1036：逃离大迷宫

输入：blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
输出：false
解释：
从源方格无法到达目标方格，因为我们无法在网格中移动。
无法向北或者向东移动是因为方格禁止通行。
无法向南或者向西移动是因为不能走出网格。

输入：blocked = [], source = [0,0], target = [999999,999999]
输出：true
解释：
因为没有方格被封锁，所以一定可以到达目标方格。

class Solution {
public:
    static const int BOUND=1000000;
    //定义哈希函数
    struct Myhasher{
        size_t operator()(const pair<int,int>& o)const{
            hash<uint64_t> fn=hash<uint64_t>();
            auto&[x,y]=o;
            return (uint64_t)x<<20|y;
        }
    };
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        if(blocked.size()<2) return true;//小于2个必定封不住
        if(bfs(blocked,source,target)==false) return false;//起点被封住
        else if(bfs(blocked,target,source)==false) return false;//终点被封住
        else return true;
    }
    bool bfs(vector<vector<int>>& blocked,vector<int>&source,vector<int>& target){
        unordered_set<pair<int,int>,Myhasher> set;
        int blockedN=blocked.size();
        int countMax=(blockedN)*(blockedN+1)/2;//走过的格子数超过这个,则没能挡住该出发点
        for(auto& pos:blocked){//把障碍物加入set中,表明这些路不能走
            set.emplace(pos[0],pos[1]);
        }
        queue<pair<int,int>> q;//queue来实现bfs
        vector<vector<int>> dirs={{1,0},{-1,0},{0,1},{0,-1}};
        q.emplace(source[0],source[1]);
        while(!q.empty()&&countMax>0){
            auto [x,y]=q.front();
            q.pop();
            for(int d=0;d<4;d++){
                int nx=x+dirs[d][0];
                int ny=y+dirs[d][1];
                if(nx>=0&&nx<BOUND&&ny>=0&&ny<BOUND&&!set.count({nx,ny})){//没有超出边界并且该格子还能走
                    if(nx==target[0]&&ny==target[1]) return true;
                    set.emplace(nx,ny);//走过的格子标记不能再走
                    --countMax;
                    q.emplace(nx,ny);
                }
            }
        }
        if(countMax>0) return false;//没有超过最大格子数,就不能再走了,说明路被封住了
        return true;//source作为起始点,没有被封住
    }
};