Use breadth-first search to find the shortest route in a grid.
What to build
A program that finds the fewest moves from S to G in a maze.
Requirements
- Squares:
Sstart,Ggoal,.floor,#wall. Each move goes one square up, down, left or right. - Print the fewest number of moves, or
no path.
Input
Line 1: rows and columns. Then the rows.
Output
One line.
Constraints
At most 50 × 50 squares; exactly one S and one G.
Example
Input:
3 4
S..#
.#..
...G
Output:
5
Why it works
Breadth-first search reaches every square in order of distance, so the first time it reaches G is by a shortest route.
Examples
Example 1 · Input
3 4 S..# .#.. ...G
Expected output
5
Example 2 · Input
2 3 S#G .#.
Expected output
no path
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Run breadth-first search from S, storing the number of steps to each square when it is first reached.
Hint 2
Moves go up, down, left and right into squares that are not walls.
Solution
Show one correct solution (try it yourself first)
from collections import deque
rows, cols = map(int, input().split())
grid = [input() for _ in range(rows)]
start = next((r, row.index("S")) for r, row in enumerate(grid) if "S" in row)
dist = {start: 0}
queue = deque([start])
answer = "no path"
while queue:
r, c = queue.popleft()
if grid[r][c] == "G":
answer = dist[(r, c)]
break
for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and (nr, nc) not in dist:
dist[(nr, nc)] = dist[(r, c)] + 1
queue.append((nr, nc))
print(answer)