问题 L: 吃蛋糕
内存限制:256 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:16
解决:8
题目描述
一天,小D来到了一个迷宫,迷宫里有一个蛋糕,小D想去把这个蛋糕吃掉。小D的手上现在有一张迷宫的地图,这张地图有R行,每行有 C个方格。
每个方格中有一个字符,字符有四种:
- # (井字号)表示墙。
- . (点号)表示空地。
- S (大写字母S)表示你开始的位置。
- C (大写字母C)表示蛋糕的位置。
小D只能在空地上行走,从一个空地走到另一个相邻的空地。
此外,地图上所描绘的矩形区域完全被墙壁所包围。
为了尽快地吃到蛋糕,小D获取了一支传送枪,其功能如下:
小D可以在任何时间,任何地点,向上、左、下、右四个方向中的一个发射传送门。当一个传送门被发射了之后,它就会一直向发射的方向飞行,直到碰触到墙壁。这时,传送门会被固定放置在这堵墙上。
只允许有两座传送门同时存在,如果已经有两个传送门被放置在迷宫里,那么其中一个(由小D选定)将在再次使用传送枪时被立即移除。在一个现有的门上放置传送门将代替原来的传送门(在墙壁的每一侧最多有一座传送门)注意,在同一堵墙壁的不同侧面可能有两个传送门。
当有两个传送门同时存在时,小D可以使用它们来传送自己。当小D位于一个传送门前时,他可以进入这个传送门并到达另一个传送门所在的位置,传送和移动一格同样消耗一个单位时间。
假设进出传送门不需要时间,并且在两个相邻的方块之间移动或通过传送门传送需要一个时间单位。
给出迷宫的地图以及小D的起始位置和蛋糕的位置,请你计算出你吃到蛋糕所需的最短时间。
输入
输入的第一行包含两个整数:
R和 C,表示迷宫的行数和列数。
接下来的 R行,每行 C个字符,表示整个迷宫。
保证字符 S和 C都只出现一次。
输出
输出应该包含一个整数:从起始位置到达蛋糕所需的最短时间。
样例输入 复制
4 4
.#.C
.#.#
....
S...
样例输出 复制
4
提示
最快速的移动顺序如下:
- 向右移动。
- 向右移动,向上发射一个传送门,向下发射一个传送门。
- 进入底部传送门。
- 向右移动一格,然后吃到蛋糕
R<=1000,C<=1000