题目描述

给定一个 $R\times C$ 的迷宫，每个格子都有一种方块：

• # 墙，不可以走，不可以穿过
• . 路，可以走
• S 出生点，玩家从这里开始走，只有一个
• C 终点，玩家要到达这里，只有一个

现在要对迷宫进行扩容，周围要增加一个方块 #，变成 $(R+2)\times (C+2)$ 的迷宫。

并且在任何时候，它都可以向上、左、下、右四个方向中的一个发射传送门。当一个传送门被发射，它会一直向发射的方向飞行，直到碰触到墙壁。这时，传送门会被放置在这堵墙上。

走一格需要 $1$ 的时间，穿梭传送门也需要 $1$ 的时间。

求从出生点到终点最少需要多少时间。

如果很难理解题意，请配合样例进行理解。

输入格式

第一行两个整数 $R,C$ 代表迷宫大小。
接下来 $R$ 行每行 $C$ 个字符代表迷宫。

输出格式

一行一个整数代表到达终点的最小时间。

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

4

提示

样例说明

对于样例 $1$，我们把迷宫模拟出来并且在周围加上 # 之后，如下图所示：

人形物体为 S，蛋糕形物体为 C。

如图所示，至少需要 $4$ 的时间。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（11 pts）：$R,C \le 10$。
• Subtask 2（20 pts）：$R,C \le 50$。
• Subtask 3（20 pts）：$R,C \le 200$，每个 . 周围都至少有一个 #。
• Subtask 4（19 pts）：$R,C \le 200$。
• Subtask 5（30 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le R,C \le 1000$。

本题强制 $O2$ 优化。

说明

翻译自 BalticOI 2014 Day2 B Portals。