题目内容

考古队在古道中发现了一个神秘的宝箱，宝箱需要按特定顺序收集文物碎片才能解锁。请你在一个 $n \times m$ 的网格中行动：

• $0$ 表示可通行的空地
• $1$ 表示障碍物（无法通过）
• $2$ 表示起点
• $3$ 表示宝箱位置
• $4-9$ 表示文物碎片（数字代表碎片编号）

考古队需从起点出发，按照序号依次收集碎片并进入宝箱。每移动 $1$ 格的单位时间消耗为 $1$，移动时不能斜向移动。若存在多条路径，需选择耗时最短的方案。

注意点： $1$. 碎片必须按编号升序收集（如先收集 $4$ 再收集 $5$）。 $2$. 允许碎片编号不连续（举例：网格中只有 $4,6$ 两块碎片，也能打开宝箱） $3$. 碎片编号重复时需要都收集（举例：网格中有两块 $4$ 号碎片和一块 $5$ 号碎片，则要收集两块 $4$ 号碎片和一块 $5$ 号碎片才能打开宝箱），每个碎片重复次数上限为 $3$。 $4$. 网格的最大为 $20 \times 20$。 $5$. 保证存在至少一条有效路径，障碍物必须绕行，碎片等障碍物地点均可通行。

输入描述

• 第一行：$n$ 和 $m$
• 后续 $n$ 行：每行 $m$ 个整数，表示网格状态

输出描述

输出最短的总耗时

样例1

输入

4 5
2 0 0 0 0
1 0 4 0 0
1 0 1 5 0
1 0 1 1 3

输出

7

说明

起点位置(0,0)到碎片 $4(1,2)$ 最短耗时： $3$；

碎片 $4(1,2)$ 到碎片 $5(2,3)$ 最短耗时： $2$；

碎片 $5(2,3)$ 到宝箱 $(3,4)$ 最短耗时： $2$；

总计耗时：$3+2+2=7$

样例2

输入

5 5
0 2 0 0 0
0 1 0 4 0
0 1 0 1 5
0 1 0 6 1
0 1 0 0 3

输出

13

说明

起点位置 $(0,1)$ 到碎片 $4(1,3)$ 最短耗时： $3$；

碎片 $4(1,3)$ 到碎片 $5(2,4)$ 最短耗时： $2$；

碎片 $5(2,4)$ 到碎片 $6(3,3)$ 最短耗时： $6$（碎片 $5$ 到 碎片 $6$ 之间有障碍物需要绕路：$(2,4)->(1,4)->(1,3)->(1,2)->(2,2)->(3,2)->(3,3)$）

碎片 $6(3,3)$ 到宝箱 $(4,4)$ 最短耗时： $2$

总计耗时：$3+2+3+5=13$