Medium

The Maze II

LAB

A ball rolls until hitting a wall. Return the shortest rolling distance to stop at destination, or -1.

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
12

FUNCTION SHAPE

maze: intMatrixstart: intArraydestination: intArray→int

SOLUTION NOTE

Very standard.

Reveal reference solution +

pythonREFERENCE

def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
    m, n = len(maze), len(maze[0])
    dist = [[float('inf')] * n for _ in range(m)]
    dist[start[0]][start[1]] = 0
    heap = [(0, start[0], start[1])]  # (distance, x, y)

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

    while heap:
        d, x, y = heapq.heappop(heap)
        if [x, y] == destination:
            return d
        if d > dist[x][y]:
            continue
        for dx, dy in directions:
            nx, ny, steps = x, y, 0
            # roll the ball until it hits a wall
            while 0 <= nx + dx < m and 0 <= ny + dy < n and maze[nx + dx][ny + dy] == 0:
                nx += dx
                ny += dy
                steps += 1
            if d + steps < dist[nx][ny]:
                dist[nx][ny] = d + steps
                heapq.heappush(heap, (d + steps, nx, ny))

    return -1

TimeO(m*n*log(m*n))

SpaceO(m*n)

Open on LeetCode ↗