Exercise 7: Shortest Path (BFS)

Your Task

Write a function shortest_path_length(maze) that:

• Finds the shortest path from (0, 0) to the bottom-right corner
• Returns the number of cells in that path
• Returns -1 if no path exists
• 0 = wall, 1 = open path
• Uses BFS (not recursion)

---

Why BFS and not DFS?

DFS might find a path, but not necessarily the shortest one. BFS explores cells in order of distance from the start, so the first time it reaches the destination, that's guaranteed to be the shortest path.

---

BFS Template

from collections import deque

queue = deque([(0, 0, 1)])  # (row, col, distance)
visited = {(0, 0)}

while queue:
    row, col, dist = queue.popleft()

    # Check if destination
    # ...

    # Explore neighbors
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        r, c = row + dr, col + dc
        if valid and not visited:
            visited.add((r, c))
            queue.append((r, c, dist + 1))

---

Examples

maze1 = [
    [1, 1, 0],
    [0, 1, 0],
    [0, 1, 1]
]
print(shortest_path_length(maze1))  # 5
# Path: (0,0)→(0,1)→(1,1)→(2,1)→(2,2) = 5 cells

maze2 = [
    [1, 0],
    [0, 1]
]
print(shortest_path_length(maze2))  # -1 — no path

---

Hints