LeetCode Solutions

			

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>&& visited) {
    if (i < 0 || i >= 1e6 || j < 0 || j >= 1e6 ||
        blockedSet.count(hash(i, j)) || visited.count(hash(i, j)))
      return false;

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

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

			

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> visited) {
    if (i < 0 || i >= 1e6 || j < 0 || j >= 1e6 || blockedSet.contains(hash(i, j)) ||
        visited.contains(hash(i, j)))
      return false;

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

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

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

			

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], visited: set) -> bool:
      if not 0 <= i < 10**6 or not 0 <= j < 10**6 or (i, j) in blocked or (i, j) in visited:
        return False

      visited.add((i, j))
      if len(visited) > (1 + 199) * 199 // 2 or [i, j] == target:
        return True
      return dfs(i + 1, j, target, visited) or \
          dfs(i - 1, j, target, visited) or \
          dfs(i, j + 1, target, visited) or \
          dfs(i, j - 1, target, visited)

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