Third Avenue

题目描述

有一个城镇表示为一个具有 $H$ 行横向和 $W$ 列纵向的二维网格。
字符 $a_{i,j}$ 描述从上数第 $i$ 行从左数第 $j$ 列的方格。这里，$a_{i,j}$ 为下面之一：$S$、$G$、$.$、#、$a$、... 和 $z$。

表示不能进入的方格，$a$、...、$z$ 表示带有传送器的方格。

Takahashi 最初在表示为 $S$ 的方格中。每一秒，他将做以下动作之一：

前往与当前位置水平或垂直相邻且不是 # 的方格。 选择一个与他当前位置字符相同的方格，并传送到该方格。只有当他位于表示为 $a$、... 或 $z$ 的方格时，才能使用此动作。

求 Takahashi 从表示为 $S$ 的方格到表示为 $G$ 的方格所需的最短时间。
如果目的地不可到达，则输出 $-1$。

输入格式

输入从标准输入按以下格式给出： $H$ $W$ $a_{1,1}\dots a_{1,W}$ $\vdots$ $a_{H,1}\dots a_{H,W}$

输出格式

输出 Takahashi 从表示为 $S$ 的方格到表示为 $G$ 的方格所需的最短时间。
如果目的地从初始位置不可到达，则输出 $-1$。

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

4

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

14

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

-1

提示

$1 \le H, W \le 2000$ $a_{i,j}$ 是 $S$、$G$、$.$、# 或小写英文字母。 恰有一个方格表示为 $S$ 且一个方格表示为 $G$。记 $(i, j)$ 表示从上数第 $i$ 行从左数第 $j$ 列的方格。
最初，Takahashi 在 $(1, 1)$。 一种在四秒内到达 $(2, 5)$ 的方法是：

从 $(1, 1)$ 走到 $(2, 1)$； 从 $(2, 1)$ 传送到 $(2, 3)$，它也是一个 $a$ 方格； 从 $(2, 3)$ 走到 $(2, 4)$； 从 $(2, 4)$ 走到 $(2, 5)$。

标签: AtCoder|abc184E

来源

AtCoder|abc184E