Skip to content

1036. Escape a Large Maze 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
 public:
  bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source,
                        vector<int>& target) {
    unordered_set<long> blockedSet;
    for (const vector<int>& b : blocked)
      blockedSet.insert(hash(b[0], b[1]));

    return dfs(blockedSet, source[0], source[1], hash(target[0], target[1]),
               {}) &&
           dfs(blockedSet, target[0], target[1], hash(source[0], source[1]),
               {});
  }

 private:
  bool dfs(unordered_set<long>& blockedSet, int i, int j, long target,
           unordered_set<long>&& seen) {
    if (i < 0 || i >= 1e6 || j < 0 || j >= 1e6 ||
        blockedSet.contains(hash(i, j)) || seen.contains(hash(i, j)))
      return false;

    seen.insert(hash(i, j));
    if (seen.size() > (1 + 199) * 199 / 2 || hash(i, j) == target)
      return true;
    return dfs(blockedSet, i + 1, j, target, std::move(seen)) ||
           dfs(blockedSet, i - 1, j, target, std::move(seen)) ||
           dfs(blockedSet, i, j + 1, target, std::move(seen)) ||
           dfs(blockedSet, i, j - 1, target, std::move(seen));
  }

  long hash(int i, int j) {
    return (static_cast<long>(i) << 16) + j;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
  public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
    Set<Long> blockedSet = new HashSet<>();
    for (int[] b : blocked)
      blockedSet.add(hash(b[0], b[1]));

    return dfs(blockedSet, source[0], source[1], hash(target[0], target[1]), new HashSet<>()) &&
        dfs(blockedSet, target[0], target[1], hash(source[0], source[1]), new HashSet<>());
  }

  private boolean dfs(Set<Long> blockedSet, int i, int j, long target, Set<Long> seen) {
    if (i < 0 || i >= 1e6 || j < 0 || j >= 1e6 || blockedSet.contains(hash(i, j)) ||
        seen.contains(hash(i, j)))
      return false;

    seen.add(hash(i, j));
    if (seen.size() > (1 + 199) * 199 / 2 || hash(i, j) == target)
      return true;

    return                                         //
        dfs(blockedSet, i + 1, j, target, seen) || //
        dfs(blockedSet, i - 1, j, target, seen) || //
        dfs(blockedSet, i, j + 1, target, seen) || //
        dfs(blockedSet, i, j - 1, target, seen);
  }

  private long hash(int i, int j) {
    return ((long) i << 16) + j;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def isEscapePossible(
      self,
      blocked: list[list[int]],
      source: list[int],
      target: list[int]
  ) -> bool:
    def dfs(i: int, j: int, target: list[int], seen: set) -> bool:
      if i < 0 or i >= 10**6 or j < 0 or j >= 10**6:
        return False
      if (i, j) in blocked or (i, j) in seen:
        return False
      seen.add((i, j))
      return (len(seen) > (1 + 199) * 199 // 2 or [i, j] == target or
              dfs(i + 1, j, target, seen) or
              dfs(i - 1, j, target, seen) or
              dfs(i, j + 1, target, seen) or
              dfs(i, j - 1, target, seen))

    blocked = set(tuple(b) for b in blocked)
    return (dfs(source[0], source[1], target, set()) and
            dfs(target[0], target[1], source, set()))