Mark what you have seen

Because a graph can have loops, if you do not remember where you have been you go back and forth between the same two nodes for ever. The cure is a seen set: you queue a node only if you have not seen it before.

1def reachable(grid, r, c, seen):
2    if not (0 <= r < len(grid) and 0 <= c < len(grid[0])):
3        return
4    if grid[r][c] == "#" or (r, c) in seen:
5        return
6    seen.add((r, c))
7    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
8        reachable(grid, r + dr, c + dc, seen)

The same walk on a grid, with recursion: first "am I inside the grid", then "is it a wall, have I been here"; if neither, mark the cell and go to the four neighbours. Keeping the four directions in a list is shorter and safer than writing four separate lines.

"Is there a way from A to B?" is this walk itself: start at A, and if B is among the seen when the walk ends, there is a way. Extra links like teleport pads only add one more edge to the neighbour list; the walk stays the same.

Tasks