문제
현석이는 주말만 되면 산에 올라가는 것을 매우 좋아라 한다. 현석이는 산을 오르기전에 꼭 산의 지도를 가지고 간다. 지도는 R행 C열의 크기로 구성되어있으며, 아무것도 없는 산길은 ‘.’, 바위 ‘X’, 목적지 ‘D’로 표시 되어있다.
어느 날 현석이는 산행 중 산불이 났다는 관리인의 방송을 들었다. 방송에서는 산불의 위치가 어디인지를 알려주었고 이미 산을 너무 많이 올라온 현석이는 입구로 내려가기엔 불이 번지는 속도보다 빠를 수가 없었다. 현석이는 지도에 불이 난 위치를 ‘F’로 표시하고 현재위치를 ‘S’로 표시한 다음 가장 빨리 목적지인 ‘D’로 가는 길을 찾으려고 한다.
불은 여러 군데서 발생했을 수도 있으며 1시간마다 지도상의 상, 하, 좌, 우로 인접한 칸으로 옮겨간다. 현석이도 1시간에 한 칸씩 상, 하, 좌, 우로 이동이 가능하다. 현석이와 불은 바위로 올라갈 수는 없으며, 목적지에는 소방시절이 잘 되어있어 불이 번지지 않는다.
입력
입력의 첫 번째 줄에는 지도 크기인 50보가 작거나 같은 R과 C가 공백으로 구분하여 들어온다.
그 다음 줄에 R x C크기의 현재 지도의 상태가 들어온다.
출력
출력은 한 줄에 현재 위치 ‘S’에서 목적지인 ‘D’까지 가는데 가장 빨리 갈수 있는 시간을 출력한다. 목적지까지 갈수 없는 경우는 “BYE”를 출력한다.
예제
3 3
D.S
FX.
...
2
힌트
로그인해야 코드를 작성할 수 있어요.