Loading...
Loading...
Loading...
A maze is a grid with S as the start, E as the exit, . as open floor and # as a wall. You may walk through at most one wall cell on your way, as if you could break it once. Print the fewest steps from S to E, or -1 if even that is not enough. Each step moves up, down, left or right.
Example 1
Input
1 3 S#E
Output
2
Example 2
Input
1 4 S##E
Output
-1
Try the problem first. Open one hint at a time.
A state is a cell plus how many walls you have broken so far, 0 or 1.
BFS over these states: stepping onto a wall is allowed only when the count is 0, and then it becomes 1.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor