← 返回题目列表

AtCoder · abc436_d

G. 传送迷宫

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

分数: 400 点

问题陈述

有一个由网格组成的迷宫, H 行和 W 列。 让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。 细胞类型 (i,j) 作为一个字符给出 S_{i,j},其中每个字符具有以下含义:

  • . :空单元格
  • # :障碍细胞
  • 小写英文字母(a - z): 扭曲单元

在迷宫中,您可以按任意顺序执行以下两种类型的操作任意次数:

  • 行走:从当前单元格沿四个方向(上、下、左、右)之一移动到相距一个单元格的单元格。但是,您无法移动到障碍物单元或网格之外。
  • 扭曲:当你位于扭曲单元时,移动到任何写有相同字符的扭曲单元。

确定是否可以从单元格中移动 (1,1) 到单元格 (H,W),如果可能,找到所需操作的最小总数。

约束

  • 1\leq H,W \leq 1000
  • H\times W \geq 2
  • H 和 W 是整数。
  • S_{i,j} is ., #,或小写英文字母。
  • S_{1,1}\neq #
  • S_{H,W}\neq #

输入

输入由标准输入按以下格式给出:

H W
S_{1,1}S_{1,2}\dots S_{1,W}
\vdots
S_{H,1}S_{H,2}\dots S_{H,W}

输出

如果可以从单元格中移动 (1,1) 到单元格 (H,W),打印所需的最少动作总数;否则,打印 -1.


示例输入 1

3 4
..a.
####
ba#b

示例输出 1

5

您可以从单元格中移动 (1,1) 到单元格 (3,4) 通过执行以下操作:

  1. 从单元格移动 (1,1) 到单元格 (1,2) 步行。
  2. 从单元格移动 (1,2) 到单元格 (1,3) 步行。
  3. 从单元格移动 (1,3) 到单元格 (3,2) 通过扭曲。
  4. 从单元格移动 (3,2) 到单元格 (3,1) 步行。
  5. 从单元格移动 (3,1) 到单元格 (3,4) 通过扭曲。

操作总数为 5,这是最小值。


示例输入 2

3 4
..a.
####
b.#b

示例输出 2

-1

无法从单元格中移动 (1,1) 到单元格 (3,4).


示例输入 3

4 4
xxxx
xxxx
xxxx
xxxx

示例输出 3

1

示例输入 4

7 11
u..#y..#...
k..#.z.#.k.
iju#...#x..
###########
..x#.t.#..n
abc#y..#...
..z#..t#.y.

示例输出 4

12