화염에서탈출 > 문제은행

본문 바로가기


알고리즘 BFS

1082 : 화염에서탈출

제한시간: 1000 ms    메모리제한: 40 MB
해결횟수: 776 회    시도횟수: 3526 회   



지섭이는 중간계(middle-earth)에서 유명한 용자이다.


어느날 사람들에게 부탁 받은 마물 퇴치를 신속히 해결하고 집으로 돌아가려고 하는데, 마법의 숲에서 평소에 사이가 좋지 않았던 불의 마법사 명근이와 마주치게 되었다. 명근이는 지섭이를 처치하기 위해서 화염 마법을 시전하였고 어느덧 숲은 화염으로 가득차고 있었다. 지섭이는 명근이가 화염을 풀어 놓은 숲에서 신속히 요새로 귀환하고자 한다!


숲의 지도는 R행과 C열로 이뤄져있다. 비어있는 칸은 '.'로 표시되고, 불은 '*'로, 바위는 'X'로 표시되어있다. 용자의 집은 'D'로 표현되고, 지섭이가 처음에 서있는 위치는 'S'로 표시된다.


매 분마다 지섭이는 인접한 4개의 칸(상, 하, 좌, 우)으로 이동할 수 있다. 불은 매 분마다 인접한 4개의 칸에 불을 옮긴다. 지섭이는 불과 바위를 지나지 못한다. 불은 바위와 요새에 옮겨지지 않는다.


지섭이가 탈출을 할 수 있을 때 몇 분 만에 탈출 할 수 있는지 알아보는 프로그램을 작성하라.


입력의 첫번째 줄에는 50이하의 정수인 R과 C가 입력된다. 다음 줄 부터 지도가 입력되며, 이는 R개의 줄로 이뤄져있다. 각 R개의 줄에는 C개의 문자가 입력된다. 지도에는 정확히 하나의 용자의 집과 하나의 시작 위치가 입력된다.



지섭이가 숲에서 용자의 집으로 돌아올 수 있을 때 최단 시간(분)을 출력하고, 만약 탈출이 불가능할 경우 "impossible"을 출력한다.


[Copy]
3 3
D.*
...
.S.
[Copy]
3


[Copy]
3 3
D.*
...
..S
[Copy]
impossible


[Copy]
3 6
D...*.
.X.X..
....S.
[Copy]
6




bfs

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.