2022秋招备战！每天写至少一篇Leetcode里Hard难度题目的题解

1036. 逃离大迷宫

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

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

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

只有在可以通过一系列的移动从源方格 source 到达目标方格 target 时才返回 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 <= xi, yi < 106
• source.length == target.length == 2
• 0 <= sx, sy, tx, ty < 106
• source != target
• 题目数据保证 source 和 target 不在封锁列表内

方法一：广度优先搜索+提前退出

很明显本题的的图的size(1e6 * 1e6) 已经超过了正常人能接受的范围。但是反过来看的话，blocked长度只有200*200,是可以接受的范围。因此如果我们能考虑一下blocked的点能否将起点或者终点的一个点围住就可以做了。

根据基本的几何素养，block的点最好的围城结果是根据三条边围成一个三角形。因此最多可以围到m * (m - 1)/2 (m为blocked的长度)的等腰直角三角形。

因此当我们的搜索数量达到这个数字后，又或者直接遇到了终点，必定不可能被包围。

因此我们对2个点同时进行广度优先搜索，两个点都没有被包围就可以连通。

广搜的状态可以用把坐标哈希成字符串进行处理。也可以用一维化进行处理。

class Solution {
public:
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        unordered_set<string> blocks;
        const int M = 1e6;
        const int n = blocked.size();

        for (auto& block : blocked) {
            blocks.insert(to_string(block[0]) + ' ' + to_string(block[1]));
        }

        array<int, 4> dx = {0, 0, 1, -1};
        array<int, 4> dy = {1, -1, 0, 0};

        auto checkBFS = [&](vector<int>& s, vector<int>& t) {
            auto vis = blocks;
            queue<pair<int, int>> q;
            int cnt = 1; // 遍历的格子的数量
            q.emplace(s[0], s[1]);
            vis.insert(to_string(s[0]) + ' ' + to_string(s[1]));
            while(!q.empty()) {
                auto [x, y] = q.front();
                q.pop();               
                for (int k = 0; k < 4; k++) {
                    int ax = dx[k] + x, ay = dy[k] + y;
                    string tmp = to_string(ax) + ' ' + to_string(ay);
                    if (ax >= 0 && ax < M  && ay >= 0 && ay < M && vis.find(tmp) == vis.end()) {
                        ++cnt;      
                        if (cnt * 2 > n * (n - 1)) return true; // 包围失败
                        if (ax == t[0] && ay == t[1]) return true; // 包围失败
                        q.emplace(ax, ay);
                        vis.insert(tmp);
                    }
                }
            }
            return false;
        };


        return checkBFS(source, target) && checkBFS(target, source);
    }
};

方法二： 离散化+搜索

其实这题离散化是一个更好的方法..有机会回来填坑..