Shortest Clear Grid Path
Problem
A warehouse robot moves on a grid where 0 marks an open cell and 1 marks a shelf. Each move goes one cell up, down, left or right, and only onto open cells. Return the fewest moves needed to go from the top-left cell to the bottom-right cell, or -1 if it cannot be done. The grid has at least one cell.
Examples
Input: grid = [[0, 0, 0, 0],
[1, 1, 0, 1],
[0, 0, 0, 0],
[0, 1, 1, 0]]
Output: 6
Why: right twice, down twice, right once, down onceInput: grid = [[0, 1],
[1, 0]]
Output: -1
Why: both neighbours of the start are shelvesInput: grid = [[0]]
Output: 0
Why: edge case, the robot already stands on the goalHints
0 / 3
Every move costs the same, so the question is really about the fewest hops in an unweighted graph whose nodes are open cells.
Breadth-first search explores cells in order of distance from the start, so the first time it reaches a cell it has used the fewest possible moves.
Start a queue at the top-left with distance 0, after checking that neither corner is a shelf. Pop a cell, and for each open neighbour inside the grid that has no distance yet, record one more than the current distance and enqueue it. Return the goal's distance when it is popped, or -1 if the queue empties first.
Solution
Treat each open cell as a node joined to its open neighbours, and every edge costs one move. Breadth-first search visits nodes in waves of equal distance, so the distance recorded when a cell is first reached is the shortest. Recording the distance at enqueue time also marks the cell as seen, which keeps each cell in the queue at most once. Time is O(rc) for r rows and c columns, and space is O(rc).
from collections import deque
def fewest_moves(grid):
rows, cols = len(grid), len(grid[0])
if grid[0][0] or grid[rows - 1][cols - 1]:
return -1 # a blocked corner can never be used
dist = {(0, 0): 0}
queue = deque([(0, 0)])
while queue:
r, c = queue.popleft()
if (r, c) == (rows - 1, cols - 1):
return dist[r, c] # first arrival is the shortest
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and not grid[nr][nc] and (nr, nc) not in dist:
dist[nr, nc] = dist[r, c] + 1
queue.append((nr, nc))
return -1
print(fewest_moves([[0, 0, 0, 0], [1, 1, 0, 1], [0, 0, 0, 0], [0, 1, 1, 0]])) # -> 6
print(fewest_moves([[0, 1], [1, 0]])) # -> -1
print(fewest_moves([[0]])) # -> 0Stuck on the idea rather than the code? Shortest Path, Unweighted covers it.