Exercise 2 solution

    from collections import deque

    def solve(grid):
        rows = len(grid)
        cols = len(grid[0])
        start = goal = None
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "S":
                    start = (r, c)
                elif grid[r][c] == "G":
                    goal = (r, c)
        parent = {start: None}
        q = deque([start])
        while q:
            cur = q.popleft()
            if cur == goal:
                path = []
                while cur is not None:
                    path.append(cur)
                    cur = parent[cur]
                return path[::-1]
            r, c = cur
            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nr, nc = r + dr, c + dc
                if (0 <= nr < rows and 0 <= nc < cols
                        and grid[nr][nc] != "#" and (nr, nc) not in parent):
                    parent[(nr, nc)] = cur
                    q.append((nr, nc))
        return None

    maze = [
        "S.#.....",
        ".##.###.",
        "....#...",
        ".####.#.",
        "......#G",
    ]
    path = solve(maze)
    print(len(path) - 1)
    print(path)

    drawn = [list(row) for row in maze]
    for r, c in path[1:-1]:
        drawn[r][c] = "*"
    for row in drawn:
        print("".join(row))

    blocked = ["S#G"]
    print(solve(blocked))
    print(solve(["SG"]))

Output:
    15
    [(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (3, 5), (2, 5), (2, 6), (2, 7), (3, 7), (4, 7)]
    S.#.....
    *##.###.
    *...#***
    *####*#*
    ******#G
    None
    [(0, 0), (0, 1)]

A grid is a graph that never needs building: the neighbours of a cell are
the four cells around it, checked against the edges of the grid and the
walls. Breadth-first search finds the route with the fewest steps because it
explores all cells one step away, then all two steps away, and so on. The
parent dictionary doubles as the "seen" set and lets us walk back from the
goal to the start to recover the path. Returning None when the queue empties
means no route exists.