SP13076 CSLIKAR - Slikar

邪恶的皇帝 Cactus 拥有魔法酒桶，并且已经淹没了魔法森林！画家和三只小刺猬现在必须尽快返回到海狸的巢穴，以免被水淹没！魔法森林的地图由 $R$ 行 $C$ 列组成。空地用字符 `.` 表示，淹没的区域用 `*` 表示，岩石用 `X` 表示。此外，海狸的巢穴用 `D` 表示，画家和三只小刺猬用 `S` 表示。 每分钟，画家和三只小刺猬可以移动到四个相邻的区域（上、下、左或右）。每分钟，洪水也会扩散，使得所有与淹没区域至少有一个公共边的空地也被淹没。水和画家及三只小刺猬都不能穿过岩石。当然，画家和三只小刺猬不能穿过淹没的区域，水也不能淹没海狸的巢穴。 编写一个程序，给定魔法森林的地图，输出画家和三只小刺猬安全到达海狸巢穴所需的最短时间。 注意：画家和三只小刺猬不能移动到即将在同一分钟被淹没的区域。

输入的第一行包含两个整数 $R$ 和 $C$。接下来的 $R$ 行每行包含 $C$ 个字符（`.`，`*`，`X`，`D` 或 `S`）。地图将包含恰好一个 `D` 字符和恰好一个 `S` 字符。

输出画家和三只小刺猬安全到达海狸巢穴所需的最短可能时间。如果这不可能，输出单独一行 `KAKTUS`。

### 样例说明 #2 他们能做的最好就是沿着下边界走，然后沿着左边界走，并在到达巢穴前一分钟被淹没。 ### 数据范围 对于 $100\%$ 的数据，保证 $1 \le R, C \le 50$。 题面翻译由 ChatGPT-4o 提供。