Implement BFS and DFS on GridsStep 4 of 5

Shortest path

12345

Step 4: Shortest path

Maze solving. The grid holds 0 (open) and 1 (wall). Find the length of the shortest path from start to goal, moving 4-directionally over open cells only.

Write shortest_path(grid, start, goal) where start and goal are (row, col) tuples. Return the number of steps in the shortest path, or -1 if the goal is unreachable.

BFS is the tool: it explores cells in order of distance, so the first time you reach the goal you have the shortest path. Track distance alongside each queued cell. Notes:

  • The path length from a cell to itself is 0.
  • If start or goal is a wall, return -1.
  • Only step onto cells equal to 0.
Hints
Starter code
from collections import deque


def neighbors(grid, r, c):
    """Return in-bounds 4-directional neighbor coords: up, down, left, right."""
    rows = len(grid)
    cols = len(grid[0]) if rows else 0
    result = []
    for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
        if 0 <= nr < rows and 0 <= nc < cols:
            result.append((nr, nc))
    return result


def shortest_path(grid, start, goal):
    """Return BFS shortest-path length over open (0) cells, or -1 if unreachable."""
    # TODO: BFS from start, tracking distance; return dist at goal or -1
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step