Maaaaaaaaaze
시간 제한2초메모리 제한512 MB
5개의 5×5 판을 각각 자유롭게 회전하고 임의 순서로 쌓아 만든 5×5×5 정육면체에서 한 꼭짓점에서 반대편 꼭짓점까지의 최단 이동 횟수를 구한다.
문제
평화롭게 문제를 경작하며 생활하는 마을 사람들은 더 이상 2차원 미로에 흥미를 느끼지 않는다. 2차원 미로는 너무나 쉽게 탈출할 수 있기 때문이다. 미로를 세상 누구보다 사랑하는 준현이는 이 상황을 안타깝게 여겨 아주 큰 상금을 걸고 마을 사람들의 관심을 끌 3차원 미로 탈출 대회를 열기로 했다.
대회 규칙은 다음과 같다.
- 5×5 크기의 판이 5개 주어진다. 이 중 일부 칸은 참가자가 들어갈 수 있고 일부 칸은 들어갈 수 없다. 그림에서 하얀 칸은 참가자가 들어갈 수 있는 칸, 검은 칸은 들어갈 수 없는 칸을 의미한다.
- 참가자는 주어진 판을 시계 방향 또는 반시계 방향으로 자유롭게 회전할 수 있다. 그러나 판을 뒤집을 수는 없다.
- 회전을 마친 뒤 참가자는 판 5개를 쌓는다. 쌓는 순서는 참가자가 자유롭게 정할 수 있다. 이렇게 판 5개를 쌓아 만든 5×5×5 크기의 큐브가 참가자를 위한 미로이다. 이때 큐브의 입구는 정육면체에서 참가자가 임의로 선택한 꼭짓점에 위치한 칸이고, 출구는 입구와 면을 공유하지 않는 꼭짓점에 위치한 칸이다.
- 참가자는 현재 위치한 칸과 면으로 인접한 칸이 들어갈 수 있는 칸이면 그 칸으로 이동할 수 있다.
- 참가자 중 자신이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 우승한다. 미로의 입구나 출구가 막혀 있거나 입구에서 출구로 도달하는 방법이 없으면 탈출이 불가능한 것으로 본다.
이 대회에서 우승하려면 미로를 잘 빠져나오기 위한 담력 증진과 체력 훈련, 그리고 적절한 운이 가장 중요하지만, 가장 적은 이동 횟수로 출구에 도달하도록 미로를 만드는 능력도 빼놓을 수 없다. 주어진 판으로 가장 적은 이동 횟수로 출구에 도달하도록 미로를 만들었을 때 몇 번 이동해야 하는지 구해보자.
입력
첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 들어갈 수 있는 칸을 의미한다.
출력
첫째 줄에 주어진 판으로 설계된 미로를 탈출하는 가장 적은 이동 횟수를 출력한다. 단, 어떻게 설계하더라도 탈출이 불가능하면 -1을 출력한다.