P4328 [COCI 2006/2007 #1] Slikar

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

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

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

对第二个样例测试的说明：他们能做的最好就是沿着下边界走，然后沿着左边界走，并在到达巢穴前一分钟被淹没。 题面翻译由 ChatGPT-4o 提供。