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) {
    constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    const int m = maze.size();
    const int n = maze[0].size();
    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 (const auto& [dx, dy] : dirs) {
        int x = i;
        int y = j;
        while (isValid(maze, x + dx, y + dy)) {
          x += dx;
          y += dy;
        }
        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[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    final int m = maze.length;
    final int n = maze[0].length;
    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[] dir : dirs) {
        int x = i;
        int y = j;
        while (isValid(maze, x + dir[0], y + dir[1])) {
          x += dir[0];
          y += dir[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:
    dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
    m = len(maze)
    n = len(maze[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 dx, dy in dirs:
        x = i
        y = j
        while isValid(x + dx, y + dy):
          x += dx
          y += dy
        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:
  static constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-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 (const auto& [dx, dy] : dirs) {
      int x = i;
      int y = j;
      while (isValid(maze, x + dx, y + dy)) {
        x += dx;
        y += dy;
      }
      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}, {1, 0}, {0, -1}, {-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[] dir : dirs) {
      int x = i;
      int y = j;
      while (isValid(maze, x + dir[0], y + dir[1])) {
        x += dir[0];
        y += dir[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:
    dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
    m = len(maze)
    n = len(maze[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 dx, dy in dirs:
        x = i
        y = j
        while isValid(x + dx, y + dy):
          x += dx
          y += dy
        if dfs(x, y):
          return True

      return False

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