Maze Solver
Find the shortest path through a grid maze with breadth-first search.
๐งฉ Problem statement
The maze is a list of text rows: # walls, . open, S start, E exit. Moving up/down/left/right, find the length of the shortest path from S to E using BFS, or show “No path”.
๐ Requirements
- Grid
- BFS
- DFS (extension)
- Backtracking (extension)
- Path finding
๐ฅ Inputs
- MAZE: list of rows
๐ค Outputs
- Shortest number of steps, or No path
๐ Rules
- No diagonal moves
- Canโt pass walls
๐ง Constraints
- Up to 20 ร 20
๐งญ Suggested approach
- Find S and E
- BFS from S with a queue of [row, col, steps]
- Mark visited cells in a set of "r,c" keys
๐ง Required concepts
- Graphs
- Queues
- Sets
- Nested lists
Design your solution here. Use Run to dry-run it step by step and Run tests to check it. Hints unlock one at a time โ try on your own first!
๐งช Edge cases to test
- No path exists
- S next to E
- A maze thatโs one long corridor
๐ Complexity analysis
BFS visits each cell at most once: O(rows ร cols) time and memory (a real hash set makes the visited check O(1)).
๐ Solution walkthrough (open after youโve tried!)
The maze is a graph: cells are nodes and moves are edges. BFS explores cells in order of distance from the start, so the first time it reaches E is guaranteed to be the shortest path. Each queue entry carries its step count; the SEEN set prevents revisiting cells.
๐ Challenge extensions
- Print the actual path (remember each cellโs parent)
- Solve with DFS + backtracking and compare
- Add keys and doors
