1036

1036. Escape a Large Maze (Hard)

There is a 1 million by 1 million grid on an XY-plane, and the coordinates of each grid square are (x, y).

We start at the source = [sx, sy] square and want to reach the target = [tx, ty] square. There is also an array of blocked squares, where each blocked[i] = [xi, yi] represents a blocked square with coordinates (xi, yi).

Each move, we can walk one square north, east, south, or west if the square is not in the array of blocked squares. We are also not allowed to walk outside of the grid.

Return true if and only if it is possible to reach the target square from the source square through a sequence of valid 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 cannot move.
We cannot move north or east because those squares are blocked.
We cannot move south or west because we cannot go outside of the grid.

Example 2:

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

 

Constraints:

• 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
• It is guaranteed that source and target are not blocked.

Companies:
Uber, UiPath

Related Topics:
Array, Hash Table, Depth-First Search, Breadth-First Search

Solution 1. DFS

If we can search a point whose distance to the source is >= 200, then we know that source must not be enclosed by the blocked points. The same for the target point. If both direction are not blocked, we can return true.

If source meets target within this search process, we can return true.

Otherwise, we return false.

// OJ: https://leetcode.com/problems/escape-a-large-maze/
// Author: github.com/lzl124631x
// Time: O(?)
// Space: O(?)
class Solution {
public:
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        unordered_map<int, unordered_set<int>> blk;
        for (auto &b : blocked) blk[b[0]].insert(b[1]);
        int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
        auto check = [&](vector<int> &from, vector<int> &to) -> int { // 0 -> blocked, 1 -> source & target met, 2 -> from is not enclosed by blocked points
            unordered_map<int, unordered_set<int>> seen;
            function<int(int, int, int)> dfs = [&](int x, int y, int dist) {
                if (x == to[0] && y == to[1]) return 1;
                if (dist >= 200) return 2;
                for (auto &[dx, dy] : dirs) {
                    int a = x + dx, b = y + dy;
                    if (a < 0 || b < 0 || a >= 1e6 || b >= 1e6 || (blk.count(a) && blk[a].count(b)) || seen[a].count(b)) continue;
                    seen[a].insert(b);
                    int ans = dfs(a, b, abs(a - from[0]) + abs(b - from[1]));
                    if (ans) return ans;
                }
                return 0;
            };
            return dfs(from[0], from[1], 0);
        };
        int a = check(source, target);
        return a == 1 || (a == 2 && check(target, source));
    }
};