Hedge Maze Exit
MediumGraphs
Problem
A garden hedge maze is drawn as a list of equal-length strings maze: # is hedge, . is open path, S is where you stand and E is the exit. There is exactly one S and one E.
Each step moves you one cell up, down, left or right onto a non-hedge cell. Return the minimum number of steps to reach the exit, or -1 if it cannot be reached.
Example 1
- Input:
- maze = ["S.#", ".##", "..E"]
- Output:
- 4
Go down twice, then right twice: (0,0) → (1,0) → (2,0) → (2,1) → (2,2).
Example 2
- Input:
- maze = ["S#E"]
- Output:
- -1
The hedge in the middle blocks the only way.
Constraints
- 1 ≤ rows, cols ≤ 1000
- rows · cols ≤ 10^5
- maze contains exactly one 'S' and one 'E'.
Hint
Show the first hint
Every step costs the same. Which traversal finds shortest paths when all edges weigh 1?
Walkthrough
How to approach it
01Clarify before coding
- Can I step on S and E like normal cells? Yes, both are walkable.
- Are diagonal moves allowed? No, four directions only.
- What if E is unreachable? Return -1.
02Brute force
Use DFS to enumerate every simple path from S to E and keep the shortest.
Cost: Exponential in the number of open cells: the number of simple paths in an open grid explodes long before 10^5 cells.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.