490. The Maze

Approach 1: BFS

• Time: $O(mn)$
• Space: $O(mn)$

C++JavaPython

class Solution {
 public:
  bool hasPath(vector<vector<int>>& maze, vector<int>& start,
               vector<int>& destination) {
    const int m = maze.size();
    const int n = maze[0].size();
    const vector<int> dirs{0, 1, 0, -1, 0};
    queue<pair<int, int>> q{{{start[0], start[1]}}};
    vector<vector<bool>> seen(m, vector<bool>(n));
    seen[start[0]][start[1]] = true;

    while (!q.empty()) {
      const auto [i, j] = q.front();
      q.pop();
      for (int k = 0; k < 4; ++k) {
        int x = i;
        int y = j;
        while (isValid(maze, x + dirs[k], y + dirs[k + 1])) {
          x += dirs[k];
          y += dirs[k + 1];
        }
        if (x == destination[0] && y == destination[1])
          return true;
        if (seen[x][y])
          continue;
        q.emplace(x, y);
        seen[x][y] = true;
      }
    }

    return false;
  }

 private:
  bool isValid(const vector<vector<int>>& maze, int x, int y) {
    return 0 <= x && x < maze.size() && 0 <= y && y < maze[0].size() &&
           maze[x][y] == 0;
  }
};

class Solution {
  public boolean hasPath(int[][] maze, int[] start, int[] destination) {
    final int m = maze.length;
    final int n = maze[0].length;
    final int[] dirs = {0, 1, 0, -1, 0};
    Queue<int[]> q = new ArrayDeque<>(Arrays.asList(new int[] {start[0], start[1]}));
    boolean[][] seen = new boolean[m][n];
    seen[start[0]][start[1]] = true;

    while (!q.isEmpty()) {
      final int i = q.peek()[0];
      final int j = q.poll()[1];
      for (int k = 0; k < 4; ++k) {
        int x = i;
        int y = j;
        while (isValid(maze, x + dirs[k], y + dirs[k + 1])) {
          x += dirs[k];
          y += dirs[k + 1];
        }
        if (x == destination[0] && y == destination[1])
          return true;
        if (seen[x][y])
          continue;
        q.offer(new int[] {x, y});
        seen[x][y] = true;
      }
    }

    return false;
  }

  private boolean isValid(int[][] maze, int x, int y) {
    return 0 <= x && x < maze.length && 0 <= y && y < maze[0].length && maze[x][y] == 0;
  }
}

class Solution:
  def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
    m = len(maze)
    n = len(maze[0])
    dirs = [0, 1, 0, -1, 0]
    q = collections.deque([(start[0], start[1])])
    seen = {(start[0], start[1])}

    def isValid(x: int, y: int) -> bool:
      return 0 <= x < m and 0 <= y < n and maze[x][y] == 0

    while q:
      i, j = q.popleft()
      for k in range(4):
        x = i
        y = j
        while isValid(x + dirs[k], y + dirs[k + 1]):
          x += dirs[k]
          y += dirs[k + 1]
        if [x, y] == destination:
          return True
        if (x, y) in seen:
          continue
        q.append((x, y))
        seen.add((x, y))

    return False

Approach 2: DFS

• Time: $O(mn)$
• Space: $O(mn)$

C++JavaPython

class Solution {
 public:
  bool hasPath(vector<vector<int>>& maze, vector<int>& start,
               vector<int>& destination) {
    return dfs(maze,
               vector<vector<bool>>(maze.size(), vector<bool>(maze[0].size())),
               start[0], start[1], destination);
  }

 private:
  const vector<int> dirs{0, 1, 0, -1, 0};

  bool dfs(vector<vector<int>>& maze, vector<vector<bool>>&& seen, int i, int j,
           const vector<int>& destination) {
    if (i == destination[0] && j == destination[1])
      return true;
    if (seen[i][j])
      return false;

    seen[i][j] = true;

    for (int k = 0; k < 4; ++k) {
      int x = i;
      int y = j;
      while (isValid(maze, x + dirs[k], y + dirs[k + 1])) {
        x += dirs[k];
        y += dirs[k + 1];
      }
      if (dfs(maze, move(seen), x, y, destination))
        return true;
    }

    return false;
  }

  bool isValid(const vector<vector<int>>& maze, int x, int y) {
    return 0 <= x && x < maze.size() && 0 <= y && y < maze[0].size() &&
           maze[x][y] == 0;
  }
};

class Solution {
  public boolean hasPath(int[][] maze, int[] start, int[] destination) {
    boolean[][] seen = new boolean[maze.length][maze[0].length];
    return dfs(maze, seen, start[0], start[1], destination);
  }

  private static final int[] dirs = {0, 1, 0, -1, 0};

  private boolean dfs(int[][] maze, boolean[][] seen, int i, int j, int[] destination) {
    if (i == destination[0] && j == destination[1])
      return true;
    if (seen[i][j])
      return false;

    seen[i][j] = true;

    for (int k = 0; k < 4; ++k) {
      int x = i;
      int y = j;
      while (isValid(maze, x + dirs[k], y + dirs[k + 1])) {
        x += dirs[k];
        y += dirs[k + 1];
      }
      if (dfs(maze, seen, x, y, destination))
        return true;
    }

    return false;
  }

  private boolean isValid(int[][] maze, int x, int y) {
    return 0 <= x && x < maze.length && 0 <= y && y < maze[0].length && maze[x][y] == 0;
  }
}

class Solution:
  def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
    m = len(maze)
    n = len(maze[0])
    dirs = [0, 1, 0, -1, 0]

    seen = set()

    def isValid(x: int, y: int) -> bool:
      return 0 <= x < m and 0 <= y < n and maze[x][y] == 0

    def dfs(i: int, j: int) -> bool:
      if [i, j] == destination:
        return True
      if (i, j) in seen:
        return False

      seen.add((i, j))

      for k in range(4):
        x = i
        y = j
        while isValid(x + dirs[k], y + dirs[k + 1]):
          x += dirs[k]
          y += dirs[k + 1]
        if dfs(x, y):
          return True

      return False

    return dfs(start[0], start[1])