1897: 洪水

一天，   一个画家在森林里写生，突然爆发了山洪，他需要尽快返回住所中，那里是安

全的。

森林的地图由R行C列组成，空白区域用点“.”表示，洪水的区域用“*”表示，而

岩石用“X”表示，另画家的住所用“D”表示，画家用“S”表示。

有以下几点需要说明：

1、  每一分钟画家能向四个方向移动一格（上、下、左、右）

2、  每一分钟洪水能蔓延到四个方向的相邻格子（空白区域）

3、  洪水和画家都不能通过岩石区域

4、  画家不能通过洪水区域（同时也不行，即画家不能移到某个格子，该格子在画家达到的同时被洪水蔓延到了，这也是不允许的）

5、  洪水蔓不到画家的住所。

给你森林的地图，编写程序输出最少需要花费多长时间才能从开始的位置赶回家中。

输入第一行包含两个整数R和C(R,C<=50)。

接下来R行每行包含C个字符(“.”、“*”、“X”、“D”或“S”)。地图保证只有一个“D”和一个“S”。

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

3 3 
D.*
...
.S.

3