[BalticOI 2014 Day2] Portals
题目描述
给定一个 $R\times C$ 的迷宫，每个格子都有一种方块：
- `#` 墙，不可以走，不可以穿过
- `.` 路，可以走
- `S` 出生点，玩家从这里开始走，只有一个
- `C` 终点，玩家要到达这里，只有一个
现在要对迷宫进行扩容，周围要增加一个方块 `#`，变成 $(R+2)\times (C+2)$ 的迷宫。
并且在任何时候，它都可以向上、左、下、右四个方向中的一个发射传送门。当一个传送门被发射，它会一直向发射的方向飞行，直到碰触到墙壁。这时，传送门会被放置在这堵墙上。
走一格需要 $1$ 的时间，穿梭传送门也需要 $1$ 的时间。
求从出生点到终点最少需要多少时间。
如果很难理解题意，请配合样例进行理解。
输入输出格式
输入格式
第一行两个整数 $R,C$ 代表迷宫大小。
接下来 $R$ 行每行 $C$ 个字符代表迷宫。
输出格式
一行一个整数代表到达终点的最小时间。
输入输出样例
输入样例 #1
4 4
.#.C
.#.#
....
S...输出样例 #1
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](https://boi.cses.fi/files/boi2014_day2.pdf)。