【题目描述】

给定 $H\times W$ 的网格。# 是障碍，. 是空地，小写字母 a 到 z 是传送门。

每次操作可以：

• 移动到上下左右相邻的非障碍格；
• 如果当前位于字母格，可以传送到任意另一个相同字母格。

两种操作都花费 $1$。求从 $(1,1)$ 到 $(H,W)$ 的最少操作数；无法到达时输出 -1。

【输入格式】

$H$   $W$

$s_1$

$\vdots$

$s_H$

【输出格式】

输出最少操作数，或 -1。

【样例】

3 5
.a#..
.#a#.
.....

5

【数据范围】

• $1\le H,W\le1000$
• $(1,1)$ 与 $(H,W)$ 不是障碍