一位冒险者进入了一个迷宫中寻宝。他手上已经拥有了一份这个迷宫的地图,其中标注了迷宫的完整结构以及迷宫中每个宝箱所在的位置。
迷宫的地图是一个由m*n个格子组成的平面图,纵向的上下方向上每列有m个格子,横向的左右方向上每行有n个格子,其中每个格子为不能进入的障碍格或可以进入的通行格。如果有两个上下相邻或左右相邻的通行格,则可以从其中一个通行格走到另一个通行格。每个宝箱放置在不同的通行格中。
他的目标是收集到这个迷宫里的所有宝箱,因此他给自己在这个迷宫中寻宝制定了如下策略:
1. 计算出离他当前位置曼哈顿距离最小的未收集宝箱,如果有多个就选定最小编号那个,记为k号宝箱;
2. 如果他当前位置无法到达k号宝箱,则收集失败,流程结束;否则,计算出他当前位置到k号宝箱的最短路径长度,并且按上下左右的次序依次计算出如果向这个方向走一格通行格之后,到k号宝箱的最短路径长度是否有缩短,如果有缩短则往这个方向走一格;
3. 如果他当前所在位置有未收集宝箱,就收集这个宝箱。如果所有宝箱已经被收集,则收集完成。否则回到第1步并重复执行。
两个位置间的一条路径,是指从其中一个位置开始,通过若干个相邻通行格,走到另一个位置,其中经过的通行格顺序。两个位置的最短路径,是指这两个位置的所有路径中,通过的通行格数量最少的路径。两个位置的最短路径长度,是指沿这两个位置的最短路径走的格数。