Shortest path through a grid

Enumerating every simple route and keeping the shortest is a correct baseline but can explore exponentially many routes on an open grid. Greedily moving toward the goal fails immediately on the pictured shelf: the first required move increases Manhattan distance. DFS's first path is also not necessarily shortest.

Use a FIFO queue and a parent map. Insert the start with no parent. When visiting a cell, generate the four neighbors, discard outside/wall/discovered positions, record the parent, and enqueue. On reaching the goal, follow parent links backward and reverse. Never mark the input grid, because the caller still displays it.

cells leave the queue in nondecreasing distance, and each saved parent is one step closer to the start. First discovery is shortest because no later parent can have a smaller distance. Mark on enqueue to bound the frontier; otherwise two neighboring cells can enqueue the same position repeatedly.

For R rows and C columns, validation/search take O(RC) time. Parent map and queue use O(RC) auxiliary space in the worst case; the returned route uses O(P) for P cells. Copying a full path into every queue entry would add avoidable path-length cost. Parent pointers retain exactly the information reconstruction needs.

Follow-up 1 — allow diagonal moves. Predict the new shortest distance. If corner cutting is allowed, the pictured route drops to four moves through the bottom middle cell. If diagonals may not pass between a shelf and a boundary, neighbor generation must check the adjacent orthogonal cells too. Define this policy before changing the algorithm.

Follow-up 2 — terrain costs vary. FIFO layers now measure moves, not cost. Use Dijkstra for nonnegative costs and define whether cost belongs to entering a cell or traversing an edge. A* may reduce exploration with an admissible heuristic; the correctness claim must name that heuristic and the movement rules.

Senior depth is connecting neighbor policy, the shortestness proof, and tests for mutation/unreachability. Lead depth adds map-version consistency for live requests.

Reference: solution.py (download file, source below); tests verify a forced detour, open-grid distance, unchanged input, blocked endpoints, and malformed maps.

"""Four-direction unit-cost BFS; input is never changed."""
from collections import deque


def shortest_grid_path(grid, start, goal):
    if not grid or not grid[0] or any(len(row) != len(grid[0]) for row in grid):
        raise ValueError("nonempty rectangular grid required")
    rows, cols = len(grid), len(grid[0])
    if any(cell not in (0, 1) for row in grid for cell in row):
        raise ValueError("cells must be 0 (open) or 1 (wall)")
    for point in (start, goal):
        if (len(point) != 2 or any(not isinstance(x, int) for x in point)
                or not 0 <= point[0] < rows or not 0 <= point[1] < cols):
            raise ValueError("endpoint outside grid")
    start, goal = tuple(start), tuple(goal)
    if grid[start[0]][start[1]] or grid[goal[0]][goal[1]]:
        return []
    queue = deque([start])
    parent = {start: None}
    while queue:
        cell = queue.popleft()
        if cell == goal:
            path = [cell]
            while parent[path[-1]] is not None:
                path.append(parent[path[-1]])
            return path[::-1]
        r, c = cell
        for nr, nc in ((r + 1, c), (r, c + 1), (r - 1, c), (r, c - 1)):
            neighbor = (nr, nc)
            if (0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0
                    and neighbor not in parent):
                parent[neighbor] = cell
                queue.append(neighbor)
    return []

python -m unittest discover -s curriculum/01-code/02-data-structures-algorithms/problems/24-grid-shortest-path -p 'test_*.py'