填空题

迷宫寻宝-研发

Question

一位冒险者进入了一个迷宫中寻宝。他手上已经拥有了一份这个迷宫的地图，其中标注了迷宫的完整结构以及迷宫中每个宝箱所在的位置。

迷宫的地图是一个由m*n个格子组成的平面图，纵向的上下方向上每列有m个格子，横向的左右方向上每行有n个格子，其中每个格子为不能进入的障碍格或可以进入的通行格。如果有两个上下相邻或左右相邻的通行格，则可以从其中一个通行格走到另一个通行格。每个宝箱放置在不同的通行格中。

他的目标是收集到这个迷宫里的所有宝箱，因此他给自己在这个迷宫中寻宝制定了如下策略：

1. 计算出离他当前位置曼哈顿距离最小的未收集宝箱，如果有多个就选定最小编号那个，记为k号宝箱；

2. 如果他当前位置无法到达k号宝箱，则收集失败，流程结束；否则，计算出他当前位置到k号宝箱的最短路径长度，并且按上下左右的次序依次计算出如果向这个方向走一格通行格之后，到k号宝箱的最短路径长度是否有缩短，如果有缩短则往这个方向走一格；

3. 如果他当前所在位置有未收集宝箱，就收集这个宝箱。如果所有宝箱已经被收集，则收集完成。否则回到第1步并重复执行。

其中迷宫中两个位置的曼哈顿距离，是指这两个位置在上下方向的行差，加上左右方向的列差。如果用公式表示，如果两个位置分别为(x, y)和(u, v)，则这两个位置的曼哈顿距离为|x-u|+|y-v|。

两个位置间的一条路径，是指从其中一个位置开始，通过若干个相邻通行格，走到另一个位置，其中经过的通行格顺序。两个位置的最短路径，是指这两个位置的所有路径中，通过的通行格数量最少的路径。两个位置的最短路径长度，是指沿这两个位置的最短路径走的格数。

问在这种策略下收集所有宝箱，他需要走多少格？

数据范围：，，

进阶：时间复杂度，空间复杂度

输入描述：

输入第一行为一个正整数T，表示有T组数据。

每组数据的第一行为两个正整数m和n，分别表示迷宫地图的行数和列数。

接下来有m行，每行有n个字符，表示迷宫地图中这行每一个中的图例表示。图例如下：

#: 障碍格；

*: 冒险者当前位置，为通行格；

0-9: 每个宝箱所在位置，为通行格；

.: 其它通行格

其中冒险者当前位置在一个迷宫地图中是有且仅有一个的。表示宝箱的数字，在一个迷宫地图中最多只会出现一次，且如果有一个k（k>0)号宝箱在迷宫地图中，则k-1号宝箱也必定会在迷宫地图中。

 

数据范围：

对于所有数据，满足1<=T<=5, 1<=m<=50, 1<=n<=50。

输入样例： 3 5 5 0...1 .#.#. ..*.. .#.#. 2...3 5 5 0...1 .#.#. ..*.# .#.#. 2.#.3 5 5 ....1 .#### ..*.. ####. 0.... 输出描述：

对于每一组数据，输出一个正整数。如果冒险者能收集完所有宝箱，则输出他共走了多少格，否则输出-1。

输出样例 16 -1 -1