SP19216 SMARIO - Super Mario Revisited

超级马里奥是历史上最经典的电子游戏之一。在这个问题中，我们再次帮助马里奥去拯救公主。游戏中，每个世界都由一个二维矩形网格表示。有多个这样的世界，每个世界大小为 $R \times C$。每个格子仅能容纳一个物体。 - ‘S’ 表示马里奥的起始位置。 - ‘.’ 表示马里奥可以安全走过的空单元格。马里奥可以从一个空单元格移动到它相邻的四个单元格之一。 - ‘D’ 表示通往下一个世界的管道。 - ‘U’ 表示通往上一个世界的管道。进入带有管道的单元格后，马里奥必须使用管道。 - ‘C’ 表示硬币，马里奥收集硬币后，该单元格变为空单元格。 - ‘#’ 表示砖块，马里奥无法进入。 - ‘M’ 标识怪物（库巴），马里奥必须击败库巴才能拯救公主。游戏的开始，马里奥处于一个空单元格。 马里奥非常坚定，一对一地打败库巴没有问题。但他也非常贪婪，总是想在拯救公主之前收集所有的硬币。如果不能收集齐所有的硬币，他将不去救援。请帮助马里奥找出完成此任务的最少步数。 特别提示： - 如果最上层世界中出现 'U' 或最下层世界中出现 'D'，马里奥无法进入这些单元格。

输入包含多个测试用例（最多1000个）。 每个测试用例的第一行包含三个整数 $R$, $C$, $W$，其中 $R \times C$ 表示网格的大小，$W$ 表示世界的数量。接下来是 $R \times W$ 行，每行包含 $C$ 个字符。 前 $R$ 行描述第一个世界，后续 $R$ 行描述第二个世界，以此类推，直到第 $W$ 个世界。 输入以 “0 0 0” 结束。

对于每个测试用例，如果马里奥能成功击败怪物并拯救公主，输出“Mario saved the princess in K steps”，其中 $K$ 是所需的最少步数；否则输出“Mario failed to save princess”。

- $1 \le R, C \le 15$ - $1 \le W \le 10$ - 硬币总数 $\le 10$ - 网格中的字符均为 ‘S’, ‘.’, ‘M’, ‘C’, ‘D’, ‘U’, ‘#’ ### 输入样例： ``` 2 2 1 SM .D 2 2 2 SM .D C. .U 3 3 2 S.M C.# D.. ### C.C C.U 2 2 1 SM #C 0 0 0 ``` ### 输出样例： ``` Mario saved the princess in 1 steps Mario saved the princess in 7 steps Mario saved the princess in 8 steps Mario failed to save princess ``` ### 第三个测试用例的说明： 马里奥起始位置在 (0,0, 1)（第一个世界），最优路径是： (0,0,1) -> (1,0,1) -> (2,0,1) -> (2,0,2) -> (1,0,2) -> (1,1,2) -> (1,2,2) -> (2,2,2) -> (2,2,1) -> (1,2,1) -> (1,2,0)。总共需要走 10 步，其中包括 1 次上行和 1 次下行。由于在不同世界之间移动不需要额外步数，减去这两步后，答案是 8 步。 **本翻译由 AI 自动生成**