题目描述

有一个由 $H$ 行和 $W$ 列的网格组成的迷宫。令 $(i,j)$ 表示从上到下第 $i$ 行、从左到右第 $j$ 列的单元格。每个单元格 $(i,j)$ 的类型由字符 $S_{i,j}$ 给出，含义如下：

• .：空单元格
• #：障碍单元格
• 小写英文字母（a – z）：传送单元格

在迷宫中，你可以按任意顺序、任意次数执行以下两种操作：

• 行走：从当前单元格移动到四个方向（上、下、左、右）之一相邻的单元格。不能移动到障碍单元格或网格外。
• 传送：当位于一个传送单元格时，可以立即移动到任意一个标记有相同字母的其他传送单元格。

请判断是否可以从单元格 $(1,1)$ 移动到单元格 $(H,W)$。如果可能，请找出所需的最少操作次数。

输入格式

第一行输入两个整数 $H, W$ ($1 \leq H, W \leq 1000$)

接下来输入 $H$ 行字符串

每行字符串有 $W$ 个字符，由小写字母、'.'和'#'字符串 $s$ ，代表每个单元格的字符

输入保证 $H \times W \geq 2$

输入保证单元格 $(1,1)$ 和单元格 $(H,W)$ 不是 ‘#’。

输出格式

如果可以从单元格 $(1,1)$ 移动到单元格 $(H,W)$，则输出所需的最小总动作数；否则输出 -1。

输入输出样例

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

5

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

-1