Problem H: [Noip模拟题]洪水

Problem H: [Noip模拟题]洪水

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 4  Solved: 3
[Submit][Status][Web Board]

Description

一天, 一个画家在森林里写生,突然爆发了山洪,他需要尽快返回住所中,那里是安全的。森林的地图由R行C列
组成,空白区域用点"."表示,洪水的区域用"*"表示,而岩石用"X"表示,另画家的住所用"D"表示,画家用"S"表
示。
有以下几点需要说明:
1、每一分钟画家能向四个方向移动一格(上、下、左、右)
2、每一分钟洪水能蔓延到四个方向的相邻格子(空白区域)
3、洪水和画家都不能通过岩石区域
4、画家不能通过洪水区域(同时也不行,即画家不能移到某个格子,该格子在画家达到的同时被洪水蔓延到了,这也是不允许的)
5、洪水蔓不到画家的住所。
给你森林的地图,编写程序输出最少需要花费多长时间才能从开始的位置赶回家中。

Input

输入第一行包含两个整数R和C(R,C<=50)。
接下来R行每行包含C个字符("."、"*"、"X"、"D"或"S")。地图保证只有一个"D"和一个"S"。

Output

输出画家最快安全到达住所所需的时间,如果画家不可能安全回家则输出"KAKTUS"。

Sample Input

3 3 
D.* 
... 
.S. 

Sample Output

3

HINT

[Submit][Status]