分数: 500 点
问题陈述
有一个城镇,用二维网格表示, H 水平行和 W 垂直列。
一个字符 a_{i,j} 描述了位于 i从顶部算起的第行和 j左起第 列。在这里, a_{i,j} 是以下之一: S , G , . , # , a,...,以及 z.
# 代表无法输入的方块,并且 a, ..., z 代表带有传送器的方块。
高桥最初位于表示为的方格处 S。每一秒,他都会做出以下动作之一:
- 转到非
#与当前位置水平或垂直相邻的正方形。 - 选择一个与当前位置具有相同字符的方格,然后传送到该方格。他只有在位于如下所示的方格时才能使用此动作
a,...,或z.
求高桥到达表示为的正方形所需的最短时间 G 来自表示为 S.
如果目的地不可达,报告 -1 代替。
约束
- 1 \le H, W \le 2000
- a_{i,j} is
S,G,.,#,或小写英文字母。 - 恰好有一个正方形表示为
S和一个正方形表示为G.
输入
输入由标准输入按以下格式给出:
H W
a_{1,1}\dots a_{1,W}
\vdots
a_{H,1}\dots a_{H,W}
输出
打印 Takahashi 到达表示为的正方形所需的最短时间 G 来自表示为 S.
如果从初始位置无法到达目的地,则打印 -1 代替。
示例输入 1
2 5 S.b.b a.a.G
示例输出 1
4
让 (i, j) 表示位于 i从顶部算起的第行和 j左起第 列。
最初,高桥位于 (1, 1)。
一种到达方式
四秒内的 (2, 5) 是:
- 从 (1, 1) to (2, 1);
- 传送自 (2, 1) to (2, 3),这也是
a方形; - 从 (2, 3) to (2, 4);
- 从 (2, 4) to (2, 5).
示例输入 2
11 11 S##...#c... ...#d.#.#.. ..........# .#....#...# #.....bc... #.##......# .......c..# ..#........ a.......... d..#...a... .#........G
示例输出 2
14
示例输入 3
11 11 .#.#.e#a... .b..##..#.. #....#.#..# .#dd..#..#. ....#...#e. c#.#a....#. .....#..#.e .#....#b.#. .#...#..#.. ......#c#G. #..S...#...
示例输出 3
-1