LeetCode Solutions

			

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 = 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