16칸 퍼즐
Problem 244
출제 일시 : 2020-11-04 00:09:31, ☕ 14
아마도 15 퍼즐 게임을 아실 것입니다. 우리나라에서는 16칸 숫자퍼즐이라는 이름으로 알려졌습니다. 여기서는 번호 붙인 타일 대신에, 7개의 빨간 타일과 8개의 파란 타일을 사용합니다.
이동은 각 방향의 영문 첫글자 대문자 (L:왼쪽, R:오른쪽, U:위, D:아래)를 이용하여 표현합니다. 즉, 상태 (S)에서 시작해서 LULUR 순서로 이동하면 상태 (E)가 됩니다:
| (S) |  | , (E) |  |
각 이동 경로에서 검사합(checksum)을 다음과 같이 계산합니다(의사코드):
checksum = 0
checksum = (checksum × 243 + m1) mod 100 000 007
checksum = (checksum × 243 + m2) mod 100 000 007
…
checksum = (checksum × 243 + mn) mod 100 000 007
여기서 mk는 이동 순서 중 k번째 문자의 ASCII 값입니다. 각 문자의 ASCII값은 다음과 같습니다:
checksum = (checksum × 243 + m1) mod 100 000 007
checksum = (checksum × 243 + m2) mod 100 000 007
…
checksum = (checksum × 243 + mn) mod 100 000 007
| L | 76 |
| R | 82 |
| U | 85 |
| D | 68 |
위의 이동 순서 LULUR에서, 최종 검사합은 19761398입니다.
이제, 상태 (S)에서 시작해서 상태 (T)에 도달하는 최단 경로를 모두 찾으세요.
| (S) | | , (T) |  |
모든 최단 길이 경로의 검사합을 다 더하면 얼마입니까?