You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC184E] Third Avenue

题目描述

给出一张 $H\times W$ 的地图，起点为 S ，终点为 G，# 表示墙体，. 表示空地。

地图上有若干个传送门，用小写字母表示。

每一秒，您可以移动到相邻位置（但不能移动到墙体），或是通过您当前所处的传送门移动到对应的任一传送门（即可以从一个字母处移动到和它相同的任意一个字母处，每次移动耗时1秒）。

问从起点到终点需要的最短时间，若是无法到达输出 -1。

输入格式

第一行两个整数 $H,W$ ，接下来 $H$ 行每行 $W$ 个字符表示这个地图。

输出格式

一个整数表示答案，如果能从起点到终点输出最短时间，否则输出 -1。

样例 #1

样例输入 #1

2 5
S.b.b
a.a.G

样例输出 #1

4

样例 #2

样例输入 #2

11 11
S##...#c...
...#d.#.#..
..........#
.#....#...#
#.....bc...
#.##......#
.......c..#
..#........
a..........
d..#...a...
.#........G

样例输出 #2

14

样例 #3

样例输入 #3

11 11
.#.#.e#a...
.b..##..#..
#....#.#..#
.#dd..#..#.
....#...#e.
c#.#a....#.
.....#..#.e
.#....#b.#.
.#...#..#..
......#c#G.
#..S...#...

样例输出 #3

-1

数据范围

• $1\ \le\ H,\ W\ \le\ 2000$
• $a_{i,j}$ 为 S , G , . , # , 或者小写英文字母

Sample Explanation 1

记第 $i$ 行第 $j$ 列的格子为 $(i,\ j)$ ，则最短路线为： $(1,\ 1)\rightarrow(2,\ 1)\rightarrow(2,\ 3)\rightarrow(2,\ 4\rightarrow(2,\ 5)$。