Shortest path in a maze

Find the fewest steps from the top-left to the bottom-right of a grid, moving up, down, left or right. # is a wall.

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

from collections import deque
def shortest(grid):
    R, C = len(grid), len(grid[0])
    q, dist = deque([(0, 0)]), {(0, 0): 0}
    while q:
        r, c = q.popleft()
        if (r, c) == (R - 1, C - 1): return dist[(r, c)]
        for dr, dc in ((1,0),(0,1),(-1,0),(0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '#' and (nr, nc) not in dist:
                dist[(nr, nc)] = dist[(r, c)] + 1
                q.append((nr, nc))
    return -1