Maaaaaaaaaze
Time limit2sMemory limit512 MB
Given five 5x5 boards, rotate each freely, stack them in any order, then find the shortest path through the resulting 5x5x5 cube from one corner to the opposite corner.
- Level
Hard8 of 10
- Topics
- Brute force, BFS, Implementation, Backtracking
- Solved
- No attempts yet
Problem
The villagers who live peacefully cultivating problems no longer take interest in two-dimensional mazes, because escaping a two-dimensional maze is far too easy. Junhyeon, who loves mazes more than anyone in the world, found this situation regrettable and decided to hold a three-dimensional maze escape contest with a very large prize to draw the villagers' attention.
The rules of the contest are as follows.
- Five 5×5 boards are given. Some cells of a board can be entered by a contestant, and some cannot. In the pictures, a white cell is a cell a contestant can enter, and a black cell is a cell a contestant cannot enter.
- A contestant can freely rotate each given board clockwise or counterclockwise. A board cannot be flipped over, however.
- After finishing the rotations, the contestant stacks the five boards. The contestant can freely choose the stacking order. The 5×5×5 cube made by stacking the five boards in this way is the maze for the contestant. The entrance of the cube is the cell at a vertex the contestant chooses freely, and the exit is the cell at the vertex that does not share a face with the entrance.
- From the cell the contestant is currently in, if a face-adjacent cell can be entered, the contestant can move to that cell.
- Among the contestants, the one who escapes the maze they designed in the fewest moves wins. If the entrance or exit of the maze is blocked, or if no way exists to reach the exit from the entrance, the maze counts as inescapable.
To win this contest, courage training, physical training, and a bit of luck matter most for getting out of a maze well, but the ability to build a maze that reaches the exit in the fewest moves cannot be left out either. Given the boards, find how many moves are needed when a maze is built so that the exit is reached in the fewest moves.
Input
The boards are given over 25 lines starting from the first line. Each board is given over 5 lines, and each line contains 5 numbers separated by spaces. 0 means a cell a contestant cannot enter, and 1 means a cell a contestant can enter.
Output
On the first line, print the fewest number of moves to escape the maze designed from the given boards. If escape is impossible no matter how the maze is designed, print -1.