1036.逃离大迷宫——hard

在一个 10^6 x 10^6 的网格中，每个网格块的坐标为 (x, y)，其中 0 <= x, y < 10^6。
我们从源方格 source 开始出发，意图赶往目标方格 target。每次移动，我们都可以走到网格中在四个方向上相邻的方格，只要该方格不在给出的封锁列表 blocked 上。
只有在可以通过一系列的移动到达目标方格时才返回 true。否则，返回 false。

示例 1：
**
输入：blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
输出：false
解释：
从源方格无法到达目标方格，因为我们无法在网格中移动。

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

提示：

• 0 <= blocked.length <= 200
• blocked[i].length == 2
• 0 <= blocked[i][j] < 10^6
• source.length == target.length == 2
• 0 <= source[i][j], target[i][j] < 10^6
• source != target

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/escape-a-large-maze

思路：

读题可知,图很大,障碍物很少。包围的方式有多种，但是可bfs次数最多的应该如下所示。因此只需要判断当前bfs次数是否超过(n*(n+1))/2(n为blocks长度).
|S O O O O O O X
|O O O O O O X
|O O O O O X
|O O O O X
.O O O X
.O O X
.O X        E  
|X

这个很暴力的做法最后双百了,可能用js交的人太少了吧。
复杂度分析：
时间复杂度O(n) (n为blocks的长度)
空间复杂度O(n)

/**
 * @param {number[][]} blocked
 * @param {number[]} source
 * @param {number[]} target
 * @return {boolean}
 */
var isEscapePossible = function (blocked, source, target) {
    let blocks = new Set();
    for (let block of blocked) {
        blocks.add(`${block[0]}:${block[1]}`);
    }
    let maxCount = (blocked.length * (blocked.length + 1)) >> 1;
    const bfs = (blocked, source, target) => {
        let queue = [[...source]];
        let top = 0;
        const dirs = [[-1, 0], [0, -1], [1, 0], [0, 1]];
        let vis = new Set();
        const path = `${source[0]}:${source[1]}`;
        vis.add(path);
        let limit = 1e6;
        while (queue.length - top > 0) {
            const front = queue[top++];
            for (let dir of dirs) {
                let newX = front[0] + dir[0];
                let newY = front[1] + dir[1];
                const path = `${newX}:${newY}`;
                if (newX < 0 || newX >= limit || newY < 0 || newY >= limit || vis.has(path) || blocks.has(path)) continue;
                if (newX === target[0] && newY === target[1]) return true;
                queue.push([newX, newY]);
                vis.add(path);
            }
            if (vis.size > maxCount) {
                return true;
            }
        }
        return false;
    };
    return bfs(blocked, source, target) && bfs(blocked, target, source);
};