Fewest Turns Maze
HardAdvanced Graphs
Problem
A warehouse robot drives on a floor plan grid of strings, where '.' is free and '#' is a shelf. It starts on the top-left cell facing any direction it likes and must reach the bottom-right cell. Driving straight ahead to the next cell is free; changing its heading (to any of the four directions) costs one turn.
Return the minimum number of turns needed to reach the goal, or -1 if it cannot be reached. Both corner cells are free.
Example 1
- Input:
- grid = ["..#","#..","#.."]
- Output:
- 2
Face right and drive to (0,1), turn down and drive to (2,1), turn right into (2,2).
Example 2
- Input:
- grid = ["...","...","..."]
- Output:
- 1
Right along the top row, one turn, then down.
Example 3
- Input:
- grid = [".#","#."]
- Output:
- -1
Constraints
- 1 ≤ rows, cols ≤ 100
- grid[r][c] ∈ {'.', '#'}
- grid[0][0] = grid[rows-1][cols-1] = '.'
Hint
Show the first hint
The cell alone is not enough state: whether the next move is free depends on the current heading.
Walkthrough
How to approach it
01Clarify before coding
- Does the initial heading cost a turn? No, the robot picks it for free.
- Is a U-turn one turn or two? One: any change of heading costs 1 (it is never useful anyway).
- Start equals goal on a 1 × 1 grid? 0 turns.
02Brute force
BFS over cells counting steps, or DFS over all paths counting heading changes.
Cost: BFS by cells minimises steps, not turns (wrong); DFS over paths is exponential.
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.