[LeetCode] 1036. Escape a Large Maze

[grandyang]

In a 1 million by 1 million grid, the coordinates of each grid square are (x, y).

We start at the source square and want to reach the target square.  Each move, we can walk to a 4-directionally adjacent square in the grid that isn't in the given list of blocked squares.

Return true if and only if it is possible to reach the target square through a sequence of moves.

Example 1:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false
Explanation: The target square is inaccessible starting from the source square, because we can't walk outside the grid.

Example 2:

Input: blocked = [], source = [0,0], target = [999999,999999]
Output: true
Explanation: Because there are no blocked cells, it's possible to reach the target square.

Constraints:

• 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

这道题说是有一个一百万乘以一百万大小的格子，有个起始坐标 source 和一个终点坐标 target，还给了一个黑名单 blocked，说是上面的点都不能经过，现在问能否从起点到达终点。首先这道题是一道 Hard 题目，要给予充分的尊重，如果你以为这是简单的迷宫遍历问题的话，那就大错特错了，为啥呢，注意看一下格子的大小，一百万乘以一百万，分分钟让你记录遍历过位置的集合爆栈，这里由于迷宫过于庞大，不一定能直接遍历到终点。其实这道题的解法挺难想的，要从黑名单的长度下手，题目中限定了黑名单的大小不超过 200，那么来思考用 200 个点能多能封闭多大的空间，如下所示：

0th      _________________________
         |O 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
200th    |X

最多能封闭 19900 个点，那么就是说若当前能够遍历到 20000 个点，则说明很大机会可以到达终点。当然极端情况下，终点可能被四个黑名单的上的点犹如围棋围杀般的包围着，所以说还需要反着遍历一般，从终点遍历点，若能在 20000 步内到达，或者达到了 20000 步，都返回 true，否则返回 false。这里可以用 BFS 来做，由于 visited 集合可能会保存 20000 个点，为了提高效率，可以将二维坐标 encode 成为一个数字，这里用横坐标乘以一百万再加上纵坐标，记得要用长整型以免整型溢出。所以这里的 visited 集合可用一个 HashSet，初始时将所有的黑名单 blocked 上的点加进去。然后进行两次 BFS 遍历，分别从起点到终点，和从终点到起点，若两次都返回 true，则整个返回 true，否则返回 false。在 BFS 子函数中，就是经典的 BFS 写法没太大的区别，唯一的不同就是用一个变量 cnt 来记录当前走过的点的个数，当到达了 20000 个，直接返回 true 即可，参见代码如下：

class Solution {
public:
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        unordered_set<long> visited;
        for (auto &a : blocked) visited.insert(a[0] * 1e6 + a[1]);
        return helper(visited, source, target) && helper(visited, target, source);
    }
    bool helper(unordered_set<long> visited, vector<int>& source, vector<int>& target) {
        int N = 1e6, cnt = 0;
        vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        queue<vector<int>> q;
        q.push(source);
        visited.insert((long)source[0] * N + source[1]);
        while (!q.empty()) {
            auto t = q.front(); q.pop();
            if (t == target) return true;
            for (auto &dir : dirs) {
                int x = t[0] + dir[0], y = t[1] + dir[1];
                if (x < 0 || x >= N || y < 0 || y >= N || visited.count((long)x * N + y)) continue;
                visited.insert((long)x * N + y);
                q.push({x, y});
                if (++cnt == 20000) return true;
            }
        }
        return false;
    }
};

Github 同步地址:

#1036

参考资料：

https://leetcode.com/problems/escape-a-large-maze/

https://leetcode.com/problems/escape-a-large-maze/discuss/282860/C%2B%2B-Limited-BFS-28-ms

https://leetcode.com/problems/escape-a-large-maze/discuss/282849/Python-BFS-and-DFS-The-whole-problem-is-broken

LeetCode All in One 题目讲解汇总(持续更新中...)