AT_abc436_d [ABC436D] Teleport Maze

有一个由 $H$ 行 $W$ 列组成的迷宫。我们用 $(i,j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。每个格子的类型由一个字符 $S_{i,j}$ 给定，具体含义如下： - `.`：空格子 - `#`：障碍格子 - 小写英文字母（`a` - `z`）：传送格子 你可以不限次数、顺序进行以下两种操作： - 行走：从当前位置移动到相邻的上下左右四个方向的其中一个格子，但不能走到障碍格或出界。 - 传送：当你在一个传送格上时，可以立刻移动到任何一个字符相同的传送格上。 请你判断是否可以从 $(1,1)$ 出发，移动到 $(H,W)$。如果可以，请输出所需的最少操作次数；否则输出 $-1$。

输入从标准输入读入，格式如下： > $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 如样例，你可以按如下顺序操作从 $(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 无法从 $(1,1)$ 到达 $(3,4)$。 ### 数据范围 - $1\leq H,W \leq 1000$ - $H\times W \geq 2$ - $H$、$W$ 均为整数 - $S_{i,j}$ 只可能为 `.`、`#` 或小写英文字母 - $S_{1,1} \neq \texttt{\#}$ - $S_{H,W} \neq \texttt{\#}$ 由 ChatGPT 5 翻译