题目描述

在一个 10^6 x 10^6 的网格中，每个网格块的坐标为 (x, y)，其中 0 <= x, y < 10^6。

我们从源方格 source 开始出发，意图赶往目标方格 target。每次移动，我们都可以走到网格中在四个方向上相邻的方格，只要该方格 不 在给出的封锁列表 blocked 上。

只有在可以通过一系列的移动到达目标方格时才返回 true。否则，返回 false。

样例

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

输入：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

算法

(宽度优先搜索 / BFS) $O(m^2)$

1. 由于 block 列表的长度 $m$ 最多只有 200，而网格却有 10^6 x 10^6。如果最终不能从起点到终点，则从起点 或 终点出发能到达的格子数量不超过 $\frac{m^2}{2}$；如果起点和终点 都 超过了这么多可达的格子，则一定能从起点到终点。（考虑极端情况，起点在角上，$m$ 个点最多能封闭多少空间）
2. 基于此，我们先从起点开始 BFS，如果过程中遇到了终点或者可达格子个数超过了 $\frac{m^2}{2}$ 个，则返回 true；然后同理再从终点开始 BFS，二者均返回 true 则最终返回 true。

时间复杂度

• 消耗的时间为 BFS 中的可达点数，最多为 $O(m^2)$。

空间复杂度

• BFS 队列需要 $O(m^2)$ 的空间。

C++ 代码

struct hash_pair {
    inline size_t operator() (const pair<int, int> &p) const { 
        return (size_t)(p.first) * 1000000 + p.second;
    } 
};

class Solution {
public:

    bool check(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {

        queue<pair<int, int>> q;
        q.push(make_pair(source[0], source[1]));
        unordered_set<pair<int, int>, hash_pair> blocked_set;
        unordered_set<pair<int, int>, hash_pair> vis;

        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};

        for (auto &b : blocked)
            blocked_set.insert(make_pair(b[0], b[1]));

        vis.insert(make_pair(source[0], source[1]));

        while (!q.empty()) {
            if (vis.size() > blocked.size() * blocked.size() / 2)
                return true;

            auto u = q.front();

            if (u.first == target[0] && u.second == target[1])
                return true;

            q.pop();

            for(int k = 0; k < 4; k++) {
                auto v = make_pair(u.first + dx[k], u.second + dy[k]);
                if (v.first < 0 || v.first >= 1000000 || v.second < 0 || v.second >= 1000000 || 
                blocked_set.find(v) != blocked_set.end() || vis.find(v) != vis.end())
                    continue;

                vis.insert(v);
                q.push(v);

            }
        }

        return false;
    }

    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        return check(blocked, source, target) && check(blocked, target, source);
    }
};