레이팅 미적용사악한 황제 Cactus가 마법의 통을 손에 넣어 마법의 숲을 물바다로 만들어 버렸다! 화가와 세 마리 아기 고슴도치는 물을 피할 수 있는 비버의 굴로 최대한 빨리 돌아가야 한다!
마법의 숲의 지도는 \(R\)개의 행과 \(C\)개의 열로 이루어져 있다. 빈 칸은 문자 .로, 물에 잠긴 칸은 *로, 바위는 X로 표시된다. 또한 비버의 굴은 D로, 화가와 세 마리 아기 고슴도치는 S로 표시된다.
매 분마다 화가와 세 마리 아기 고슴도치는 이웃한 \(4\)개의 칸(위, 아래, 왼쪽, 오른쪽) 중 하나로 이동할 수 있다. 매 분마다 홍수도 퍼져서, 물에 잠긴 칸과 변을 하나 이상 공유하는 모든 빈 칸도 물에 잠긴다. 물도, 화가와 고슴도치도 바위를 통과할 수 없다. 당연히 화가와 고슴도치는 물에 잠긴 칸을 지날 수 없고, 물은 비버의 굴을 잠기게 할 수 없다.
마법의 숲의 지도가 주어졌을 때, 화가와 세 마리 아기 고슴도치가 비버의 굴에 안전하게 도착하는 데 필요한 최단 시간을 출력하는 프로그램을 작성하시오.
참고: 화가와 고슴도치는 (같은 분에) 곧 물에 잠길 칸으로는 이동할 수 없다.
첫째 줄에 두 정수 \(R\)과 \(C\)가 주어진다. 두 수 모두 \(50\) 이하이다.
다음 \(R\)개의 줄에는 각각 \(C\)개의 문자(., *, X, D 또는 S)가 주어진다. 지도에는 D와 S가 정확히 하나씩 있다.
화가와 세 마리 아기 고슴도치가 비버의 굴에 안전하게 도착하는 데 필요한 최단 시간을 출력한다. 불가능하다면 KAKTUS라는 단어를 한 줄에 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 50점 |
3 3
D.*
...
.S.33 3
D.*
...
..SKAKTUSThe best they can do is to go along the lower border and then the left border, and get flooded one minute before reaching the den.
3 6
D...*.
.X.X..
....S.6