문제 설명
솔로 탈출을 꿈꾸는 종욱이... 하지만 그는 올해도 크리스마스를 홀로 보낼 생각에 뜬눈으로 밤을 지세우는데... 이를 평소에 딱하게 여기시던 KoreaTech 신께서 행실이 착실한 종욱이를 위하여 그에게 한가지 은총을 배풀기로 했다고 합니다.
어느날 밤. 종욱이의 꿈 속에 등장한 KoreaTech 신은 종욱이에게 다음과 같이 말했습니다.
'들어라, 불쌍한 길 잃은 양이여.. 내 너의 솔로력을 딱히 여겨, 모쏠 마법사들 조차 가지기만 하면 반드시 애인이 생긴다는 거룩한 열쇠를 여기 미로에 숨겨 놓았느니라.'
'단, 너는 반드시 이 열쇠들 모두를 최소한의 이동만으로 찾아내어야만 그 효력을 얻을 수 있느니..."
이에 잠에서 반뜩 깨어난 종욱이의 눈앞에는 지도와 규칙서가 놓여져 있었다고 합니다.
<<지도>>
<<규칙>>
1. 지도는 . 빈 공간, $ 벽, ? 시작 지점, 그리고 알파벳 열쇠로 이루어져 있습니다.
a. 영문자 알파벳은 소문자는 열쇠를 대문자는 자신과 같은 소문자 알파벳으로 열수있는 문을 의미합니다.
i. 예를 들면 a 키는 A문을 여는데 필요한 열쇠입니다.
ii. 열쇠는 a-f까지, 그리고 문 역시 A-F까지 로 주어집니다. 열쇠보다 문이 많을 수는 없고, 문에 맞는 열쇠는 반드시 존재합니다.
iii. 열쇠는 장애물이 아니므로 통과 할 수 있습니다.
iiii. 문은 열쇠가 있을 때만 통과할 수 있습니다.
iiiii. 열쇠와 문에 해당하는 알파벳은 중복되어 주어지지 않습니다. 즉 유일성이 보장됩니다.
b. 벽은 통과할 수 없습니다.
c. 빈 공간은 아무런 제약이 없습니다.
2. 지도에서 이동할 수 있는 방향은 상하 좌우로만 가능합니다.
3. 지도에 주어진 열쇠를 다 못 모으면, 이 경우에 반드시 -1을 리턴해야 합니다.
4. 만약 결과가 -1이 아니라면, 반드시 최소 이동 거리를 리턴해야만 합니다.
자! KoreaTech 학생여러분! 여러분은 솔로킹 종욱이의 미래를 결정지을 사명을 가졌습니다~! 그에게 은총을 배풀어주세요~!
어느날 밤. 종욱이의 꿈 속에 등장한 KoreaTech 신은 종욱이에게 다음과 같이 말했습니다.
'들어라, 불쌍한 길 잃은 양이여.. 내 너의 솔로력을 딱히 여겨, 모쏠 마법사들 조차 가지기만 하면 반드시 애인이 생긴다는 거룩한 열쇠를 여기 미로에 숨겨 놓았느니라.'
'단, 너는 반드시 이 열쇠들 모두를 최소한의 이동만으로 찾아내어야만 그 효력을 얻을 수 있느니..."
이에 잠에서 반뜩 깨어난 종욱이의 눈앞에는 지도와 규칙서가 놓여져 있었다고 합니다.
<<지도>>
<<규칙>>
1. 지도는 . 빈 공간, $ 벽, ? 시작 지점, 그리고 알파벳 열쇠로 이루어져 있습니다.
a. 영문자 알파벳은 소문자는 열쇠를 대문자는 자신과 같은 소문자 알파벳으로 열수있는 문을 의미합니다.
i. 예를 들면 a 키는 A문을 여는데 필요한 열쇠입니다.
ii. 열쇠는 a-f까지, 그리고 문 역시 A-F까지 로 주어집니다. 열쇠보다 문이 많을 수는 없고, 문에 맞는 열쇠는 반드시 존재합니다.
iii. 열쇠는 장애물이 아니므로 통과 할 수 있습니다.
iiii. 문은 열쇠가 있을 때만 통과할 수 있습니다.
iiiii. 열쇠와 문에 해당하는 알파벳은 중복되어 주어지지 않습니다. 즉 유일성이 보장됩니다.
b. 벽은 통과할 수 없습니다.
c. 빈 공간은 아무런 제약이 없습니다.
2. 지도에서 이동할 수 있는 방향은 상하 좌우로만 가능합니다.
3. 지도에 주어진 열쇠를 다 못 모으면, 이 경우에 반드시 -1을 리턴해야 합니다.
4. 만약 결과가 -1이 아니라면, 반드시 최소 이동 거리를 리턴해야만 합니다.
자! KoreaTech 학생여러분! 여러분은 솔로킹 종욱이의 미래를 결정지을 사명을 가졌습니다~! 그에게 은총을 배풀어주세요~!
입력 설명
처음 줄에는 정수 T ( 1 <= T <= 10 ) 가 주어집니다. T는 총 테스트 케이스의 입력 수를 의미합니다.
각 테스트 케이스의 첫번째 줄은 지도를 이루는 폭과 높이를 의미하는 W ( 1 <= W <= 30 ) 와 H ( 1 <= H <= 30 ) 그리고 각 행에 걸쳐 그 지도를 구성하는 값들 [. (빈 공간), $ (벽), ? (시작 위치) , {a-f} (열쇠), (A-F) (문)] 이 주어지게 됩니다.
각 테스트 케이스의 첫번째 줄은 지도를 이루는 폭과 높이를 의미하는 W ( 1 <= W <= 30 ) 와 H ( 1 <= H <= 30 ) 그리고 각 행에 걸쳐 그 지도를 구성하는 값들 [. (빈 공간), $ (벽), ? (시작 위치) , {a-f} (열쇠), (A-F) (문)] 이 주어지게 됩니다.
출력 설명
모든 열쇠를 얻는데 필요한 최소한의 이동 거리를 출력해야 합니다.
입력 예시 Copy
1
5 3
$b$a$
?A...
....B
출력 예시 Copy
10