2241번 - 카멜롯 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 124 | 7 | 5 | 8.621% |
문제
아주 오래 전에, 아더왕과 원탁의 기사들은 새 해를 맞이하여 한 곳에 모이곤 했었다. 이와 비슷하게, 체스판에 한 개의 왕과 여러 개의 나이트가 놓여 있고, 이들을 하나의 칸에 모으는 경우를 생각해 보자. 킹와 나이트의 움직임은 다음과 같다.
단순히 킹과 나이트를 한 칸에 모으는 문제라면 쉽겠지만, 이 문제에서는 나이트가 킹을 자신의 말에 태우는 경우를 고려해야 한다. 즉, 킹과 한 개 이상의 나이트가 같은 칸에 놓여있을 때, 킹은 따로 움직일 수도 있고, 아니면 하나의 나이트가 타고 있는 말에 올라탈 수 있다. 킹이 말에 올라타는 것은 하나의 이동으로 세지 않으며, 올라 탄 이후에는 나이트와 똑같이 움직이게 된다. 한 번 말에 오른 킹은 다시 내릴 수는 없다.
나이트가 킹이 있는 곳까지 이동한 뒤에 킹을 태울 수도 있으며, 킹이 나이트가 있는 곳으로 이동하여 말에 오를 수도 있고, 킹과 나이트가 중간의 한 곳에서 만나서 말을 탈수도 있다.
킹과 나이트들의 초기 위치가 주어졌을 때, 이들을 한 칸에 모으기 위한 최소 이동 회수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 체스판의 크기를 나타내는 두 정수 N(1 ≤ N ≤ 40), M(1 ≤ M ≤ 26)이 주어진다. N은 행의 개수, M은 열의 개수이다. 다음 줄에는 킹의 위치를 나타내는 문자 X와 수 Y가 주어진다. X는 알파벳 대문자로 표현되며, 열 번호를 의미한다. Y는 행 번호를 의미한다. 열 번호는 알파벳 A부터 차례대로 매겨진다. 다음 줄부터는 파일의 끝까지 나이트들의 위치가 주어진다. 나이트들의 위치 역시 킹의 위치와 같은 형식으로 주어진다. 파일의 끝은 두 개의 -1로 표현된다. 나이트는 0개일 수도 있고, 체스판을 가득 채울 수도 있다. 물론 같은 위치에는 한 개의 나이트만 있을 수 있다.
출력
첫째 줄에 킹과 나이트들을 한 칸에 모으기 위한 최소 이동 회수를 출력한다. 모이는 칸은 어느 곳이든 가능하다.
예제 입력 1
8 8 D 4 A 3 A 8 H 1 H 8 -1 -1
예제 출력 1
10
힌트
B5에 모이면 된다. 첫 번째 나이트는 A3 B5로 움직이며, 두 번째 나이트는 A8 C7 B5로 움직이며, 세 번째 나이트는 H1 G3 F5 D4(킹을 말에 태우고) B5로 움직이며, 네 번째 나이트는 H8-F7-D6-B5로 움직인다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호