失落的四枚遗印

题目描述

著名探险家 内森·德雷克（Nathan Drake） 在一座新发现的古代神庙深处遭遇危机。

神庙地底布满了机关、暗门、坍塌的石砖、大量古老铭文，还有某些能让人瞬间移动的神秘符文。

你的目标是帮助 Drakes 从入口成功逃到终点，但在此之前，他必须集齐 四枚失落的“神庙遗印”（Temple Sigils），分别刻有数字 0、1、2、3。

只有集齐全部四枚遗印，终点的古代石门才会开启。

神庙中还隐藏着 古代传送符文（Runes）：

• 如果某种符文在神庙中出现了两次，则它们相互连接 —— 踩上其中一个即可瞬间传送到另一处，同样消耗一次移动。
• 若某符文并非成对存在，则其只是普通刻纹，不具备传送能力。

神庙被坍塌的墙体 # 阻挡，路径可能极度诡异，而你需要找到 在获得四枚遗印后，最短从入口通往出口石门的路径。

你能帮他从古代废墟中成功脱身吗？

正式的，神庙地图由一个 n × m 的字符矩阵构成，每个格子可能是：

• #：坍塌的墙壁，无法通过。
• .：普通空地。
• !：入口（起点）。
• @：出口（终点）。
• 数字 0 ~ 3：遗印（Sigil），走上去即可拾取。其中必须集齐 0,1,2,3 四个遗印。
• 字母 a~z：古代符文（Rune）。符文出现 两次，它们相互连接，可用于瞬移。

你每次可以从当前格子向 上下左右 移动一步，不能走出地图，也不能走进 #。

当你踩上一个符文格子，如果它恰好与另一个同款符文构成一对，你会立刻被传送到对应位置（依旧算一次移动）。

你的目标是：

在集齐数字遗印 0、1、2、3 后，到达终点出口所需的最短步数。

若无法做到，则输出 -1。

输入格式

第一行输入两个整数n和m $(5 \leq n,m \leq 1000)$,表示迷宫的长和宽。

接下来输入一个$n \times m$ 的矩阵，表示迷宫。

保证地图中：恰有一个 !（入口）、恰有一个 @（出口）、四种钥匙各恰有一个、传送门符号均为小写字母且个数小于等于26。

输出格式

输出最短步数，若不存在合法路线，输出 -1。

样例 1

5 5
!....
1203.
####a
#####
a...@

10