프로그램 명: spray
제한시간: 1 초
드디어 마지막 던전인 챔피언 로드에 입장했지만 가지고 있는 몬스터들이 너무 약해져있습니다. 강한 몬스터를 만나버리면 전멸당할 가능성이 있으니까 그 위험을 최대한 줄이고 이동하려고 합니다. 다행히도 맵 어딘가에 스프레이라는 야생 몬스터를 몇 칸 동안 회피할 수 있는 아이템과 같은 효과를 받을 수 있는 칸이 있습니다. 스프레이 효과를 받지 못한 상태로 이동해야하는 최소 이동 횟수를 출력하세요.
입력
첫 줄에 맵의 크기 R, C (1 ≤ R,C ≤ 100)가 입력됩니다. X 표시가 돼있는 곳에서 시작해 Y 표시가 돼있는 곳까지 이동해야합니다. 회피 효과를 받을 수 있는 장소는 1, 2, 3, ... , 9, A, ..., F로 표시됩니다. 각 숫자들은 16진수로 야생 몬스터를 회피할 수 있는 이동 칸 수입니다. 점으로 표시된 곳은 야생 몬스터가 나타날 수 있는 칸입니다. #는 벽으로 지나갈 수 없습니다. 참고로 스프레이 효과는 누적되지 않습니다. (남아있는 스프레이 효과가 그 칸의 스프레이 효과가 더 작은 경우에만 그 칸의 스프레이 효과를 받을 수 있습니다) X에서 Y로 가는 길이 있음은 보장됩니다.
출력
스프레이 효과를 받지 못한 상태로 이동해야하는 최소 이동 횟수를 출력하세요.
입출력 예
입력
5 5
X#3..
.#...
...#.
.2#..
..#Y.
출력
7
출처:waterloo
번역:ladown21
[질/답]
[제출 현황]
[푼 후(0)]