AI: Fewest steps through a maze

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: S start, G goal, . 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)

Lesson: Problem solving by search →