시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.5 초 512 MB180301713.600%

문제

명탐정 준하에게 범인 수색의 의뢰가 맡겨졌다. 얼마 전 여러 미술관에서 미술 작품이 도난당한 사건이 있었는데, 그 범인을 찾는 의뢰였다. 왕년에 화가로 활동했던 준하는 이 사실이 안타까워 바로 사건을 담당하기로 하였다.

도난당한 미술관의 장소들은 4 * 5 크기의 2차원 격자로 된 지도로 나타낼 수 있다. 지금까지 알려진 단서는 범인이 가장 처음에 이동을 시작한 장소와 도난당한 미술관의 장소 및 도난당한 순서, 그리고 범인의 흔적이 발견된 장소들이다. 준하의 수학적 두뇌와 예술적 감각에 의하면 범인은 자신이 잘 알고 있는 사람일 가능성이 높다. 그래서 준하는 범인의 행동 패턴이 다음과 같다고 확신하였다.

  • 범인이 이동할 때, 현재 장소에서 상하좌우 중 한 방향으로 한 칸 이동한다. 지도를 벗어나지는 않는다.
  • 범인이 지금까지 들어간 적 없는 미술관에 가면 곧바로 그 미술관에 들어가서 미술 작품을 훔쳐낸다.
  • 범인이 있던 장소에는 반드시 흔적을 남긴다. 따라서 흔적이 없는 장소에는 범인이 가지 않았음을 알 수 있다. 하지만 같은 장소를 여러 번 방문할 수는 있다.

준하는 알려진 단서로부터 범인이 이동한 최단 거리를 알아내고자 한다. 그것만 알아내면 범인을 잡을 수 있을 지도 모르니 준하를 도와주자.

입력

입력은 여러 테스트케이스로 이루어져 있다. 첫째 줄엔 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 10)

각 테스트케이스마다 첫째 줄부터 4줄에 걸쳐 4 * 5 크기의 지도가 입력으로 주어진다. 지도에서 숫자 0은 범인이 처음 이동을 시작한 장소이며, 1부터 이어지는 나머지 숫자는 도난당한 미술관의 장소를 의미한다. 9보다 큰 숫자는 A부터 시작하는 알파벳으로 표시한다. #은 범인의 흔적이 발견된 장소이며 ‘.’은 아무 연관이 없는 장소를 의미한다. 각 테스트케이스끼리는 빈 줄로 구분이 되어있다.

0 은 반드시 존재하며, 같은 숫자가 2개 이상 들어오는 경우는 없다.
 

출력

테스트케이스마다 한 줄씩 범인의 최소 이동 거리를 출력한다.

범인은 왔던 길을 다시 방문할 수 있지만, 미술관에 처음 방문할 때는 도난이 발생한 순서를 따라야 한다. 즉, 1번 장소를 방문하지 않고 2번이나 3번 장소로 이동하는 것은 불가능하다.

만약 범인의 이동이 불가능한 경우는 -1을 출력한다.

예제 입력 1

2
##2##
#.0.#
3.#.#
##1##

##2##
#.0.#
#.3.#
##1##

예제 출력 1

15
-1

출처

University > 전북대학교 > 2017 전북대학교 프로그래밍 경진대회 H번

  • 데이터를 추가한 사람: jh05013
  • 문제를 다시 작성한 사람: jh05013
  • 빠진 조건을 찾은 사람: pichulia