GESP 1-4级 -- GESP 5-8级 -- CSP-J/S --

A2629. $Slikar$

编程题普及/提高-

知识点

广度优先搜索多源BFS 网格图最短路径

题目描述

给你一个$R*C$ 的矩阵，这个矩阵由 $*$ , $.$ (点) , $D$ , $S$ , $X$ 组成，会有洪水从$*$ 处涌出，每单位时间都会淹没和其四联通的平地，$.$ (点)表示平地，$X$ 是障碍，不可通行，也不会没淹没，$S$ 是出发点，三只刺猬(?)从这里出发前往庇护所，它们只能在没有被洪水淹没的平地上移动，并且每单位时间只能移动到周围一个四联通的格子，$D$ 表示庇护所，庇护所不会被洪水淹没。

输入格式

输入第一行两个整数$R,C$ （$R,C\leq 50$ ），接下来使这个矩阵。

输出格式

输出到达庇护所的最短时间，或者输出“KAKTUS”，表示根本不可能到。

输入输出样例

输入 #1

3 3
D.*
...
.S.

输出 #1

输入 #2

3 3
D.*
...
..S

输出 #2

KAKTUS

输入 #3

3 6
D...*.
.X.X..
....S.

输出 #3

上一题去做题下一题