题目描述

本题译自 BalticOI 2014 Day2 T2「Portals」

有一个迷宫，里面放着一个蛋糕，你想去把这个蛋糕吃掉。
你有一张迷宫的地图，这张地图有 $R$ 行，每行有 $C$ 个方格。
每个方格中有一个字符，字符有四种：

• # （井字号）表示墙。

• . （点号）表示空地。

• S （大写字母S）表示你开始的位置。

• C （大写字母C）表示蛋糕的位置。

你只能在空地上行走，从一个空地走到另一个相邻的空地。
此外，地图上所描绘的矩形区域完全被墙壁所包围。

为了尽快地吃到蛋糕，你已经从 Aperture Science™ 那里获取了一支传送枪，其功能如下：
在任何时候，它都可以向上、左、下、右四个方向中的一个发射传送门。当一个传送门被发射，它会一直向发射的方向飞行，直到碰触到墙壁。这时，传送门会被放置在这堵墙上。

只允许有两座传送门同时存在，如果已经有两个传送门被放置在迷宫里，那么其中一个（由您选定）将在再次使用传送枪时被立即移除。在一个现有的门上放置传送门将代替原来的传送门（在墙壁的每一侧最多有一座传送门）注意，在同一堵墙壁的不同侧面可能有两个传送门。

当有两个传送门同时存在时，你可以使用它们来传送自己。当你位于一个传送门前时，你可以进入这个传送门并到达另一个传送门所在的位置，传送和移动一格同样消耗一个单位时间。

你可以假设进出传送门不需要时间，并且在两个相邻的方块之间移动或通过传送门传送需要一个时间单位。

给出迷宫的地图以及你的起始位置和蛋糕的位置，计算出你吃到蛋糕所需的最短时间。

输入格式

输入的第一行包含两个整数： $R$ 和 $C$ ，表示迷宫的行数和列数。
接下来的 $R$ 行，每行 $C$ 个字符，表示整个迷宫。
保证字符 $S$ 和 $C$ 都只出现一次。

输出格式

输出应该包含一个整数：从起始位置到达蛋糕所需的最短时间。
你可以认为有可能在起始位置拿到蛋糕。

4 4
.#.C
.#.#
....
S...

4

数据范围与提示