탈출

시간 제한1초메모리 제한128 MB

요약

바위와 확산하는 홍수가 있는 격자에서, 다중 시작점 BFS로 물의 도달 시간을 계산하고 고슴도치의 BFS 이동 시간과 비교해 굴까지의 최소 이동 시간을 구합니다.

문제

숲에 홍수가 나기 시작했다. 숲에는 고슴도치 한 마리가 있고, 고슴도치는 가장 가까운 친구인 비버의 굴로 최대한 빨리 도망가려고 한다.

숲의 지도는 R행 C열 격자로 주어진다. 빈 칸은 .으로, 물이 차 있는 칸은 *로, 돌은 X로 표시한다. 비버의 굴은 D, 고슴도치의 시작 위치는 S로 표시한다.

매 분마다 고슴도치는 현재 칸과 변을 공유하는 네 칸 중 하나로 이동할 수 있다. 물도 매 분마다 변을 공유하는 빈 칸으로 퍼진다. 고슴도치와 물은 돌을 지나갈 수 없고, 물은 비버의 굴로 들어가지 않는다.

고슴도치는 이미 물이 찬 칸으로 이동할 수 없으며, 다음 시간에 물이 찰 칸으로도 이동할 수 없다. 그런 칸으로 이동하면 도착하는 순간 물에 빠지기 때문이다.

지도가 주어졌을 때, 고슴도치가 비버의 굴까지 안전하게 이동하는 데 필요한 최소 시간을 구하라.

첫째 줄에 자연수 R과 C가 주어진다. 두 값은 모두 50 이하이다.

다음 R개 줄에는 숲의 지도가 주어진다. 지도에는 위에서 설명한 문자만 등장하며, D와 S는 각각 정확히 하나씩 주어진다.

고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 안전하게 도착할 수 없다면 KAKTUS를 출력한다.