分数: 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,2) 步行。
- 从单元格移动 (1,2) 到单元格 (1,3) 步行。
- 从单元格移动 (1,3) 到单元格 (3,2) 通过扭曲。
- 从单元格移动 (3,2) 到单元格 (3,1) 步行。
- 从单元格移动 (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