시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
0.5 초 | 512 MB | 180 | 30 | 17 | 13.600% |
명탐정 준하에게 범인 수색의 의뢰가 맡겨졌다. 얼마 전 여러 미술관에서 미술 작품이 도난당한 사건이 있었는데, 그 범인을 찾는 의뢰였다. 왕년에 화가로 활동했던 준하는 이 사실이 안타까워 바로 사건을 담당하기로 하였다.
도난당한 미술관의 장소들은 4 * 5 크기의 2차원 격자로 된 지도로 나타낼 수 있다. 지금까지 알려진 단서는 범인이 가장 처음에 이동을 시작한 장소와 도난당한 미술관의 장소 및 도난당한 순서, 그리고 범인의 흔적이 발견된 장소들이다. 준하의 수학적 두뇌와 예술적 감각에 의하면 범인은 자신이 잘 알고 있는 사람일 가능성이 높다. 그래서 준하는 범인의 행동 패턴이 다음과 같다고 확신하였다.
준하는 알려진 단서로부터 범인이 이동한 최단 거리를 알아내고자 한다. 그것만 알아내면 범인을 잡을 수 있을 지도 모르니 준하를 도와주자.
입력은 여러 테스트케이스로 이루어져 있다. 첫째 줄엔 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 10)
각 테스트케이스마다 첫째 줄부터 4줄에 걸쳐 4 * 5 크기의 지도가 입력으로 주어진다. 지도에서 숫자 0은 범인이 처음 이동을 시작한 장소이며, 1부터 이어지는 나머지 숫자는 도난당한 미술관의 장소를 의미한다. 9보다 큰 숫자는 A부터 시작하는 알파벳으로 표시한다. #은 범인의 흔적이 발견된 장소이며 ‘.’은 아무 연관이 없는 장소를 의미한다. 각 테스트케이스끼리는 빈 줄로 구분이 되어있다.
0 은 반드시 존재하며, 같은 숫자가 2개 이상 들어오는 경우는 없다.
테스트케이스마다 한 줄씩 범인의 최소 이동 거리를 출력한다.
범인은 왔던 길을 다시 방문할 수 있지만, 미술관에 처음 방문할 때는 도난이 발생한 순서를 따라야 한다. 즉, 1번 장소를 방문하지 않고 2번이나 3번 장소로 이동하는 것은 불가능하다.
만약 범인의 이동이 불가능한 경우는 -1을 출력한다.
2 ##2## #.0.# 3.#.# ##1## ##2## #.0.# #.3.# ##1##
15 -1
University > 전북대학교 > 2017 전북대학교 프로그래밍 경진대회 H번