1036. 逃离大迷宫 : BFS + 给定障碍物所能围成的最大面积

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

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

class Solution {
    int EDGE = (int)1e6, MAX = (int)1e5;
    long BASE = 131L;
    Set<Long> set = new HashSet<>();
    int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    public boolean isEscapePossible(int[][] blocked, int[] s, int[] t) {
        for (int[] p : blocked) set.add(p[0] * BASE + p[1]);
        int n = blocked.length;
        MAX = n * (n - 1) / 2; // 可直接使用 1e5
        return check(s, t) && check(t, s);
    }
    boolean check(int[] a, int[] b) {
        Set<Long> vis = new HashSet<>();
        Deque<int[]> d = new ArrayDeque<>();
        d.addLast(a);
        vis.add(a[0] * BASE + a[1]);
        while (!d.isEmpty() && vis.size() <= MAX) {
            int[] poll = d.pollFirst();
            int x = poll[0], y = poll[1];
            if (x == b[0] && y == b[1]) return true;
            for (int[] di : dir) {
                int nx = x + di[0], ny = y + di[1];
                if (nx < 0 || nx >= EDGE || ny < 0 || ny >= EDGE) continue;
                long hash = nx * BASE + ny;
                if (set.contains(hash)) continue;
                if (vis.contains(hash)) continue;
                d.addLast(new int[]{nx, ny});
                vis.add(hash);
            }
        }
        return vis.size() > MAX;
    }
}
复制代码

class Solution {
public:
    int EDGE = 1e6, MAX = 1e5;
    long long BASE = 13331;
    unordered_set<long long> set;
    int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& s, vector<int>& t) {
        for(auto& p : blocked) set.insert(p[0] * BASE + p[1]);
        int n = blocked.size();
        MAX = n * (n - 1) / 2; // 可直接使用 1e5
        return check(s, t) and check(t, s);
    }
    bool check(vector<int>& a, vector<int>& b){
        unordered_set<long long> vis;
        queue< pair<int,int> > q;
        q.push( {a[0], a[1]});
        vis.insert(a[0] * BASE + a[1]);
        while(q.size() and vis.size() <= MAX){
            auto t = q.front();
            q.pop();
            int x = t.first, y = t.second;
            if(x == b[0] and y == b[1]) return true;
            for(int i = 0; i < 4; i++){
                int nx = x + dir[i][0], ny = y + dir[i][1];
                if(nx < 0 or nx >= EDGE or ny < 0 or ny >= EDGE) continue;
                if(set.count(nx * BASE + ny)) continue;
                if(vis.count(nx * BASE + ny)) continue;
                q.push( {nx, ny} );
                vis.insert(nx * BASE + ny);
            }
        }
        return vis.size() > MAX;
    }
};
复制代码

EDGE, MAX, BASE, DIR = int(1e6), int(1e5), 131, [(1, 0), (-1, 0), (0, 1), (0, -1)]
class Solution:
    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:
        block = {p[0] * BASE + p[1] for p in blocked}
        n = len(blocked)
        MAX = n * (n-1)//2 # 可直接使用 1e5
        def check(a, b):
            vis = {a[0] * BASE + a[1]}
            d = deque([a])
            while len(d) and len(vis) <= MAX:
                x, y = d.popleft()
                if x == b[0] and y == b[1]:
                    return True
                for dx, dy in DIR:
                    nx, ny = x + dx, y + dy
                    if nx < 0 or nx >= EDGE or ny < 0 or ny >= EDGE:
                        continue
                    h = nx * BASE + ny
                    if h in block or h in vis:
                        continue
                    d.append((nx, ny))
                    vis.add(h)
            return len(vis) > MAX
        return check(source, target) and check(target, source)
复制代码