迷宫寻宝-研发_网易互娱笔试题

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

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

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

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

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

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

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

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

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

数据范围： $1\le T\le 5\$ ， $1\le n,m\le 50\$ ， $1\le宝箱数量k\le 10\$

进阶：时间复杂度 $O(nm)\$ ，空间复杂度 $O(nm)\$

示例1

输入

3
5 5
0...1
.#.#.
..*..
.#.#.
2...3
5 5
0...1
.#.#.
..*.#
.#.#.
2.#.3
5 5
....1
.####
..*..
####.
0....

16
-1
-1

在第一组数据中，冒险者先向上走2格，再向左走2格，收集了0号宝箱；然后向右走4格，收集了1号宝箱；然后向下走4格，收集了3号宝箱；再然后向右走4格，收集了2号宝箱，收集所有宝箱完成，共走了2+2+4+4+4=16格。

在第二组数据中，无法从当前位置走到3号宝箱所在的位置收集3号宝箱，因此无法完成收集所有宝箱的任务。

在第三组数据中，在初始位置依次执行策略：

1. 计算出与0号宝箱的曼哈顿距离为4，与1号宝箱的曼哈顿距离为4，因此选定0号宝箱；

2. 计算出当前位置到0号宝箱的最短路径长度为8，按上下左右的次序依次计算：

(1) 上方为障碍格，忽略；

(2) 下方为障碍格，忽略；

(3) 左方为通行格，如果走到左方的通行格，则到0号宝箱的最短路径长度为9，比当前的最短路径长度8大，因此不选择；

(4) 右方为通行格，如果走到右方的通行格，则到0号宝箱的最短路径长度为7，比当前的最短路径长度8小，因此向这个方向走一格。

3. 当前未收集完所有宝箱，回到策略步骤1继续执行；

4. 计算出与0号宝箱的曼哈顿距离为5，与1号宝箱的曼哈顿距离为3，因此选定1号宝箱；

5. 计算出当前位置到1号宝箱的最短路径长度为9，按上下左右的次序依次计算：

(1) 上方为障碍格，忽略；

(2) 下方为障碍格，忽略；

(3) 左方为通行格，如果走到左方的通行格，则到1号宝箱的最短路径长度为8，比当前的最短路径长度9大，因此向这个方向走一格；

6. 当前未收集完所有宝箱，回到策略步骤1继续执行。

要注意到此时，冒险者当前在初始位置上，且所有宝箱都还没有被收集，继续按策略执行的过程中，冒险者会在这个位置向右走一格再向左走一格的循环中，永远无法收集到所有宝箱。