Leetcode # 490. The Maze

https://leetcode.com/problems/the-maze

Solution

m := len(maze)
n := len(maze[0])

Time Complexity: O(m * n)
Space Complexity: O(m * n)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
    _start = [(start[0], start[1])]
    queue = collections.deque(_start)
    visited = set(_start)
    DIR = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
      r, c = queue.popleft()
      for dr, dc in DIR:
        nr, nc = r, c
        while 0 <= nr + dr < len(maze) and 0 <= nc + dc < len(maze[0]) \
              and maze[nr + dr][nc + dc] == 0:
          nr += dr
          nc += dc
        if nr == destination[0] and nc == destination[1]:
          return True
        if (nr, nc) in visited:
          continue
        next_coord = (nr, nc)
        queue.append(next_coord)
        visited.add(next_coord)
    return False

Last Updated on 2023/08/16 by A1go