一、题目

在一个 10^6 x 10^6 的网格中，每个网格上方格的坐标为 (x, y) 。

现在从源方格 source = [sx, sy] 开始出发，意图赶往目标方格 target = [tx, ty] 。数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [xi, yi] 表示坐标为 (xi, yi) 的方格是禁止通行的。

每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格不在给出的封锁列表 blocked 上。同时，不允许走出网格。

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

来源：力扣（LeetCode）
链接：原题链接

示例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 <= xi, yi < 106
source.length == target.length == 2
0 <= sx, sy, tx, ty < 106
source != target
题目数据保证 source 和 target 不在封锁列表内

二、思路

本题的游戏玩法并不复杂，通过读题能够快速理解。第一反应就是通过深度优先或广度优先算法进行搜索。但难点就在于本题的搜索范围高达10⁶ *10⁶ ,如果单纯使用DFS\BFS显然会有极高的复杂度，因此需要优化。

考虑到题目要求中阻挡点的个数不会超过200个，因此一种优化方法是去探寻出发点与目标点是否被阻挡点包围，即使在最差的情况下，也仅需搜索 (n-1)n/2个点，极大的缩小了搜索空间。

本思路采用压缩搜索矩阵，由于本身阻挡点仅有不超过200个，因此在整个棋盘中大部分的地区都是空白可走的，压缩这部分空白的区域，就可以得到一个足够小的棋盘进行经典的DFS或者BFS搜索/

压缩将从行与列两个方向进行，规则是：

• 先将blocked矩阵按行从小到大排列；
• 如果第i个阻挡点的行位置与i-1个阻挡点的行位置相等，则压缩后也相等；
• 如果第i个阻挡点的行位置与i-1个阻挡点的行位置相差1，则压缩后也相差1；
• 如果第i个阻挡点的行位置与i-1个阻挡点的行位置相差大于1，则压缩后相差2；
• 将处理后的blocked矩阵按列从小到大排列
• 同上

三、代码

代码如下：

class Solution {
    
private:
    int row = pow(10, 6)-1;
    int col = pow(10, 6)-1;
    static constexpr int dir[4][2] = {
     {
    0, 1}, {
    0, -1}, {
    1, 0}, {
    -1, 0} };		//四个方向
    struct hash_pair {
    		//以pair作为key的哈希函数
        template <class T1, class T2>
        size_t operator()(const pair<T1, T2>& p) const
        {
    
            auto hash1 = hash<T1>{
    }(p.first);
            auto hash2 = hash<T2>{
    }(p.second);
            return hash1 ^ hash2;
        }
    };
    void ZIP(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target,vector<int>& id) {
    
        blocked.push_back(source);
        blocked.push_back(target);
        sort(blocked.begin(), blocked.end(), [&](const vector<int>& a, const vector<int>& b) {
    
            return a < b;
            });
        int r_id = blocked.back()[0];
        int sourcePos = find(blocked.begin(), blocked.end(), source) - blocked.begin();
        int targetPos = find(blocked.begin(), blocked.end(), target) - blocked.begin(); 
        vector<vector<int>>::iterator it = blocked.begin() + 1;
        int posTemp1 = 0;
        int posTemp2 = blocked[0][0];
        blocked[0][0] == 0 ? blocked[0][0] = 0 : blocked[0][0] = 1;		//处理上边界
        while (it != blocked.end()) {
    		//行压缩
            if ((*it)[0] - posTemp2 > 1) {
    
                posTemp2 = (*it)[0];
                (*it)[0] = posTemp1 + 2;
                posTemp1 = (*it)[0];
                ++it;
            }
            else if((*it)[0] - posTemp2 == 1)
            {
    
                posTemp2 = (*it)[0];
                (*it)[0] = posTemp1 + 1;
                posTemp1 = (*it)[0];
                ++it;
            }
            else if ((*it)[0] - posTemp2 == 0) {
    
                posTemp2 = (*it)[0];
                (*it)[0] = posTemp1;
                posTemp1 = (*it)[0];
                ++it;
            }
        }
        source = blocked[sourcePos];
        target = blocked[targetPos];
        r_id == row ? r_id = blocked.back()[0] : r_id = blocked.back()[0] + 1;
        sort(blocked.begin(), blocked.end(), [&](const vector<int>& a, const vector<int>& b) {
    
            return a[1] < b[1];
            });
        int c_id = blocked.back()[1];
        int sp = find(blocked.begin(), blocked.end(), source) - blocked.begin();
        int tp = find(blocked.begin(), blocked.end(), target) - blocked.begin();
        vector<vector<int>>::iterator pt = blocked.begin() + 1;
        int pT1 = 0;
        int pT2 = blocked[0][1];
        blocked[0][1] == 0 ? blocked[0][1] = 0 : blocked[0][1] = 1;		//处理左边界
        while (pt != blocked.end()) {
    		//列压缩
            if ((*pt)[1] - pT2 > 1) {
    
                pT2 = (*pt)[1];
                (*pt)[1] = pT1 + 2;
                pT1 = (*pt)[1];
                ++pt;
            }
            else if ((*pt)[1] - pT2 == 1)
            {
    
                pT2 = (*pt)[1];
                (*pt)[1] = pT1 + 1;
                pT1 = (*pt)[1];
                ++pt;
            }
            else if ((*pt)[1] - pT2 == 0) {
    
                pT2 = (*pt)[1];
                (*pt)[1] = pT1;
                pT1 = (*pt)[1];
                ++pt;
            }
        }
        c_id == col ? c_id = blocked.back()[1] : c_id = blocked.back()[1] + 1;
        source = blocked[sp];
        target = blocked[tp];
        blocked.erase(blocked.begin() + max(sp, tp));
        blocked.erase(blocked.begin() + min(sp, tp));
        id = {
    r_id,c_id};		//下边界与右边界
    }
public:
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
    
        vector<int> id = {
    0,0};
        ZIP(blocked, source, target,id );
        unordered_map<pair<int, int>,int,hash_pair>map;
        for (int i = 0; i < blocked.size(); ++i) {
    		//以pair为key的哈希保存
            map.insert_or_assign({
     blocked[i][0],blocked[i][1] }, 1);
        }
        queue<pair<int, int>>qe;
        qe.emplace(source[0], source[1]);
        while (!qe.empty()) {
    		//BFS
            int x = qe.front().first;
            int y = qe.front().second;
            qe.pop();
            for (int i = 0; i < 4; ++i) {
    
                int nx = x + dir[i][0], ny = y + dir[i][1];
                if (nx >= 0 and nx <= id[0] and ny >= 0 and ny <= id[1] and map.count({
     nx,ny }) == 0) {
    
                    if (nx == target[0] and ny == target[1])
                        return 1;
                    qe.push({
     nx, ny });
                    map.insert_or_assign({
     nx,ny }, 1);
                }
                
            }
        }
        return 0;
    }
};