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

This question says that there is a grid of one million times one million, with a starting coordinate source and an ending coordinate target. It also gives a blacklist blocked, saying that the above points cannot pass through. Now ask whether you can reach the end from the starting point. First of all, this question is a Hard question, which should be fully respected. If you think this is a simple maze traversal problem, it's a big mistake. Why? Pay attention to the size of the grid, one million times one million, and let you record the collection explosion stack of traversed positions every minute. Here, because the maze is too large, you may not be able to traverse directly to the end point. In fact, the solution of this problem is difficult to think about. We should start from the length of the blacklist. The size of the blacklist is limited to no more than 200. Then consider how much space can be closed with 200 points, as shown below:

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

Up to 19900 points can be closed, which means that if 20000 points can be traversed at present, it means that there is a great chance to reach the end. Of course, in extreme cases, the end point may be surrounded by the points on the four blacklists as if they were encircled by go. Therefore, it also needs to traverse backwards. Generally, if you can reach the point from the end point within 20000 steps, or reach 20000 steps, you will return true, otherwise return false. BFS can be used here. Since the visited set may save 20000 points, in order to improve efficiency, the two-dimensional coordinate can be encode d into a number. Here, the abscissa is multiplied by one million plus the ordinate. Remember to use long integer to avoid integer overflow. Therefore, the visited set here can use a HashSet, which initially adds all the points on the blacklist blocked. Then perform BFS traversal twice, respectively from the starting point to the end point and from the end point to the starting point. If both times return true, the whole will return true; otherwise, it will return false. In the BFS subfunction, the classical BFS writing method is not much different. The only difference is that a variable cnt is used to record the number of points currently passed. When 20000 points are reached, it can directly return true. See the code below:

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 sync address:

https://github.com/grandyang/leetcode/issues/1036

reference material:

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 topic explanation summary (under continuous update...)