走格子( (starstar ))
- 时限：(1s) 内存：(256M)
Descrption
-
(CYJ) 想找到他的小伙伴 (FPJ)，(CYJ) 和 (FPJ) 现在位于一个房间里,这个房间的布置可以看成一个 (N) 行 (M) 列的矩阵,矩阵内的每一个元素会是下列情况中的一种:
- 障碍区域—这里有一堵墙(用 ‘(#)’表示).
- 这是 (CYJ) 最开始在的区域(用‘ (C) ’表示).
- 这是 (FPJ) 在的区域(用‘ (F)’表示).
- 空区域(用‘(.)’表示).
-
(CYJ) 携带了一个所谓传送枪的东西,这是一把可以创造传送门的枪械,在每一次行动中,他可以选择下列操作中的一项:
- 移向一个相邻的格子中(上,下,左,右,不能移到墙在的格子里).这个操作要消耗一个单位的时间.
- 转向一个墙(不需要相邻,只需面向即可),向其发射传送门,传送门会留在墙内面向你的地方(至多只能同时存在两扇传送门)，若墙上已经有两扇传送门，而你发射了第三扇,那么最初发射的那一扇会消失。同时,你无法在一个位置制造两扇传送门（这个操作不会耗费时间）。
- 如果他与一块墙壁相邻且面前有一扇传送门,那么他可以移动到另一扇传送门前方的格子。这个操作会耗费一个单位的时间.
-
(CYJ) 想要知道自己最少需要多少时间才能够从起点(‘(C)’)到达终点(‘(F) ’).
-
请注意:我们保证地图边缘会是一圈墙壁且一定存在 ‘(C)’,‘(F)’.
Input
- 第一行输入两个正整数 (N) 和 (M ,(4 ≤ N,M ≤ 500)).表示地图大小。
- 接下来的 (N) 行每行一个长度为 (M)的字符串.表示地形。
Output
- 你需要输出最少的到达终点的时间,如果不能到达请输出”(no)”。
Sample Input
cell.in
4 4
####
#.F#
#C.#
####
cell.out
2
#### 样例2
```plain
cell.in
6 8
########
#.##..F#
#C.##..#
#..#...#
#.....##
########
cell.out
4
```
#### 样例3
```plain
cell.in
4 5
#####
#C#.#
###F#
#####
cell.out
no
```
Sample Output
Hint
-
样例 (2) 解释
- 从(C)点 ((3,2)) 开始,我们首先向左发射传送门,再向下发射传送门,向左进入传送门,到达 ((5,2)),向右发射传送门,向下进入传送门,到达 ((5,6)),向上发射传送门,向右进入传送门,到达 ((2,6)),向右移动,到达 (F).
-
(50\%) 的数据满足：(4<= N,M <=15)；
-
(100\%) 的数据满足：(4<= N,M <=500)；
-
来源：
分析
- 如果没有传送门，此题就是一个最基础的最短路，类似这样加传送门的题其实我们也做了不少了，只不过是根据传送门的性质建边就行了。
- 分析此题的传送门的性质，任意一非墙的点 (x,y)，和它相关的传送门有上下左右共四个，我们只要到达这四个传送门中的任意一个前面，我们就可以没有花费的任意在这四个传送门间传送，所以，(x,y) 到这四个传送门前面那个空地的距离相等，取 (x,y) 到墙的最近距离。
- 这里我们有一个小优化，不用枚举每个点到四个墙的距离，我们可以把所有的墙放到队列里，然后跑一边 (bfs) 就求出了每个空点到最近墙的距离。
- 建完边后跑一边最短路即可。