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

这是qklbishe.com第12605 篇笔试面试资料
提供答案分析,通过本文《一位冒险者进入了一个迷宫中寻宝。他手上已经拥有了一份这个迷宫的地图,其中标注了迷宫的完整结构以及迷宫中每个宝箱所在的位置。 迷宫的地图是一个由m*n个格子组成的平面图,纵向的上下方向上每列有m个格子,横向的左右方向上每行有n个格子,其中每个格子为不能进入的障碍格或可以进入的通行格。如果有两个上下相邻或左右相邻的通行格,则可以从其中一个通行格走到另一个通行格。每个宝箱放置在不同的通行格中。 他的目标是收集到这个迷宫里的所有宝箱,因此他给自己在这个迷宫中寻宝制定了如下策略: 1. 计算出离他当前位置曼哈顿距离最小的未收集宝箱,如果有多个就选定最小编号那个,记为k号宝箱; 2. 如果他当前位置无法到达k号宝箱,则收集失败,流程结束;否则,计算出他当前位置到k号宝箱的最短路径长度,并且按上下左右的次序依次计算出如果向这个方向走一格通行格之后,到k号宝箱的最短路径长度是否有缩短,如果有缩短则往这个方向走一格; 3. 如果他当前所在位置有未收集宝箱,就收集这个宝箱。如果所有宝箱已经被收集,则收集完成。否则回到第1步并重复执行。 其中迷宫中两个位置的曼哈顿距离,是指这两个位置在上下方向的行差,加上左右方向的列差。如果用公式表示,如果两个位置分别为(x, y)和(u, v),则这两个位置的曼哈顿距离为|x-u|+|y-v|。 两个位置间的一条路径,是指从其中一个位置开始,通过若干个相邻通行格,走到另一个位置,其中经过的通行格顺序。两个位置的最短路径,是指这两个位置的所有路径中,通过的通行格数量最少的路径。两个位置的最短路径长度,是指沿这两个位置的最短路径走的格数。 问在这种策略下收集所有宝箱,他需要走多少格?-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

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

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

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

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

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

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

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

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

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

一位冒险者进入了一个迷宫中寻宝。他手上已经拥有了一份这个迷宫的地图,其中标注了迷宫的完整结构以及迷宫中每个宝箱所在的位置。    迷宫的地图是一个由m*n个格子组成的平面图,纵向的上下方向上每列有m个格子,横向的左右方向上每行有n个格子,其中每个格子为不能进入的障碍格或可以进入的通行格。如果有两个上下相邻或左右相邻的通行格,则可以从其中一个通行格走到另一个通行格。每个宝箱放置在不同的通行格中。    他的目标是收集到这个迷宫里的所有宝箱,因此他给自己在这个迷宫中寻宝制定了如下策略:    1. 计算出离他当前位置曼哈顿距离最小的未收集宝箱,如果有多个就选定最小编号那个,记为k号宝箱;    2. 如果他当前位置无法到达k号宝箱,则收集失败,流程结束;否则,计算出他当前位置到k号宝箱的最短路径长度,并且按上下左右的次序依次计算出如果向这个方向走一格通行格之后,到k号宝箱的最短路径长度是否有缩短,如果有缩短则往这个方向走一格;    3. 如果他当前所在位置有未收集宝箱,就收集这个宝箱。如果所有宝箱已经被收集,则收集完成。否则回到第1步并重复执行。    其中迷宫中两个位置的曼哈顿距离,是指这两个位置在上下方向的行差,加上左右方向的列差。如果用公式表示,如果两个位置分别为(x, y)和(u, v),则这两个位置的曼哈顿距离为|x-u|+|y-v|。       两个位置间的一条路径,是指从其中一个位置开始,通过若干个相邻通行格,走到另一个位置,其中经过的通行格顺序。两个位置的最短路径,是指这两个位置的所有路径中,通过的通行格数量最少的路径。两个位置的最短路径长度,是指沿这两个位置的最短路径走的格数。      问在这种策略下收集所有宝箱,他需要走多少格? 区块链毕设学生638951355号
注意每次移动之后都要重新判断目标箱子。
仅当当前遇到了宝箱,才删除一个目标箱子
从题目示例中可以看到,可能出现反复横跳的情况。
可以简单保存visited数组,记录遇到过的状态。
这里可以简单的用(剩下的宝箱数量,当前位置)来记录。
剩下的就是广度优先搜索,找到最短路径长度。
按照题目要求一步步模拟。

今天 16:53:02 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 一位冒险者进入了一个迷宫中寻宝。他手上已经拥有了一份这个迷宫的地图,其中标注了迷宫的完整结构以及迷宫中每个宝箱所在的位置。 迷宫的地图是一个由m*n个格子组成的平面图,纵向的上下方向上每列有m个格子,横向的左右方向上每行有n个格子,其中每个格子为不能进入的障碍格或可以进入的通行格。如果有两个上下相邻或左右相邻的通行格,则可以从其中一个通行格走到另一个通行格。每个宝箱放置在不同的通行格中。 他的目标是收集到这个迷宫里的所有宝箱,因此他给自己在这个迷宫中寻宝制定了如下策略: 1. 计算出离他当前位置曼哈顿距离最小的未收集宝箱,如果有多个就选定最小编号那个,记为k号宝箱; 2. 如果他当前位置无法到达k号宝箱,则收集失败,流程结束;否则,计算出他当前位置到k号宝箱的最短路径长度,并且按上下左右的次序依次计算出如果向这个方向走一格通行格之后,到k号宝箱的最短路径长度是否有缩短,如果有缩短则往这个方向走一格; 3. 如果他当前所在位置有未收集宝箱,就收集这个宝箱。如果所有宝箱已经被收集,则收集完成。否则回到第1步并重复执行。 其中迷宫中两个位置的曼哈顿距离,是指这两个位置在上下方向的行差,加上左右方向的列差。如果用公式表示,如果两个位置分别为(x, y)和(u, v),则这两个位置的曼哈顿距离为|x-u|+|y-v|。 两个位置间的一条路径,是指从其中一个位置开始,通过若干个相邻通行格,走到另一个位置,其中经过的通行格顺序。两个位置的最短路径,是指这两个位置的所有路径中,通过的通行格数量最少的路径。两个位置的最短路径长度,是指沿这两个位置的最短路径走的格数。 问在这种策略下收集所有宝箱,他需要走多少格?-笔试面试资料

提供最优质的资源集合

立即查看 了解详情