Medium

The Maze

LAB

A ball rolls until hitting a wall. Return true if it can stop exactly at destination.

EXAMPLES

Example 1

Input
{
  "maze": [
    [
      0,
      0,
      1,
      0,
      0
    ],
    [
      0,
      0,
      0,
      0,
      0
    ],
    [
      0,
      0,
      0,
      1,
      0
    ],
    [
      1,
      1,
      0,
      1,
      1
    ],
    [
      0,
      0,
      0,
      0,
      0
    ]
  ],
  "start": [
    0,
    4
  ],
  "destination": [
    4,
    4
  ]
}

Output
true

FUNCTION SHAPE

maze: intMatrixstart: intArraydestination: intArray→bool

SOLUTION NOTE

Standard BFS. DFS also works here.

Reveal reference solution +

pythonREFERENCE

def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
    m, n = len(maze), len(maze[0])
    visited = [[False]*n for _ in range(m)]
    queue = deque([tuple(start)])

    directions = [(-1,0), (1,0), (0,-1), (0,1)]   # up, down, left, right

    while queue:
        x, y = queue.popleft()
        if [x, y] == destination:
            return True
        if visited[x][y]:
            continue
        visited[x][y] = True

        for dx, dy in directions:
            nx, ny = x, y
            # Roll in the current direction until hitting a wall
            while 0 <= nx+dx < m and 0 <= ny+dy < n and maze[nx+dx][ny+dy] == 0:
                nx += dx
                ny += dy
            # Only add stopping point if not visited
            if not visited[nx][ny]:
                queue.append((nx, ny))

    return False

TimeO(m*n)

SpaceO(m*n)

Open on LeetCode ↗