← 返回题目列表

AtCoder · abc184_e

E. 第三大道

中文机器翻译题面 查看原题

分数: 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