BAZE RUNNER
Time limit1sMemory limit256 MB
A 4-wide maze has one gap per middle row; find the fewest moves to go from top-left to bottom-right when the player may also shift a row's wall left or right.
- Level
Medium7 of 10
- Topics
- BFS, Graph, Simulation, Shortest path
- Solved
- No attempts yet
Problem
Seyoung, who is taking part in the 2nd BAZE RUNNER (Bit MAZE RUNNER) contest, is determined to win this time. BAZE RUNNER is played in an N×4 maze, and the player wins by starting at the top-left cell and arriving at the bottom-right cell. The top row and the bottom row of the maze have no walls, but every row in between is blocked by walls except for a single gap wide enough for one person to pass through. During one unit of time, a player can take one of the following two actions.
- Move to an adjacent cell that is not a wall.
- The left and right edges of the maze are blocked by walls.
- Rotate the walls of the row directly below or above by one cell to the left or right.
- If a wall in the leftmost or rightmost cell is pushed out, it reappears at the opposite end.
Write a program that determines the minimum number of actions Seyoung must take to reach the goal and win.
Input
The first line gives the size of the maze, N (3 ≤ N ≤ 1000).
From the next line, N-2 lines give the information for each row between the top and bottom rows of the maze.
Each row consists of 4 bits made up of 0 (path) and 1 (wall), and each row has exactly one path.
Output
On the first line, print the minimum number of actions Seyoung needs to win.