该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

传送迷宫

题目描述

给定一个由 $H$ 行 $W$ 列组成的网格迷宫。用 $(i,j)$ 表示从上到下第 $i$ 行、从左到右第 $j$ 列的格子。

每个格子类型由字符 $S_{i,j}$ 表示：

• .：空地
• #：障碍（不可进入）
• a~z：传送格子（同字母之间可传送）

你从起点 $(1,1)$ 出发，目标到达终点 $(H,W)$。你可以执行任意次以下操作，每次操作计为 1 步：

1. 走路：从当前格子移动到上下左右相邻的一个格子（不能越界，且不能进入 #）。
2. 传送：当你站在字母格子（如 c）上时，可以瞬间移动到任意另一个同字母的格子（仍计 1 步）。

请判断能否从 $(1,1)$ 到达 $(H,W)$。若能，输出最少操作次数；否则输出 $-1$。

输入格式

从标准输入读取：

• 第一行：两个整数 $H, W$
• 接下来 $H$ 行：每行一个长度为 $W$ 的字符串，表示迷宫

输出格式

输出一个整数：

• 若能到达终点，输出最少操作次数
• 否则输出 $-1$

输入输出样例 #1

输入 #1

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

输出 #1

-1

输入输出样例 #2

输入 #2

4 4
xxxx
xxxx
xxxx
xxxx

输出 #2

1

输入输出样例 #3

输入 #3

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

输出 #3

5

输入输出样例 #4

输入 #4

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

输出 #4

12

说明/提示

• $1 \le H, W \le 1000$
• $H \times W \ge 2$
• $S_{1,1} \ne \#\ \text{且}\ S_{H,W} \ne \#$