Shortest path in a grid

Breadth-first search explores every cell 1 step away, then every cell 2 steps away, and so on. The first time it reaches the goal is the shortest route.

from collections import deque

def shortest_path(grid):
    rows, cols = len(grid), len(grid[0])
    if grid[0][0] == "#" or grid[-1][-1] == "#":
        return -1
    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)]
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == "." and (nr, nc) not in dist:
                    dist[(nr, nc)] = dist[(r, c)] + 1
                    queue.append((nr, nc))
    return -1

BFS finds shortest paths whenever every step costs the same. The dist dictionary doubles as the "visited" set, so each cell is queued once: O(rows × cols). Depth-first search would find a path, but not necessarily the shortest. When steps have different costs, you need Dijkstra's algorithm instead.