实习笔试准备(3)

news/2024/4/23 13:00:57/

1 第三题

1.1 题目描述

给定一个迷宫,找到最快从起点到达重点的路径所需要的步数。 假设迷宫如下,假定左上角坐标为(0, 0),右下角坐标为(3, 2)

1 0 -1 1

-2 0 -1 -3

2 2 0 0

-2是迷宫的起点,坐标为(0, 1)

-3是迷宫的终点,坐标为(3, 1)

-1代表障碍物,不能行走

1和2代表传送门,传送门门由正整数标示,只会成对出现。站在传送门上,能仅用一步就传送到相同数字的另一个传送i门的位置: 1只能传送到1, 2只能传送到2。站在传送门上也可以选择不传送。

从起点到终点有若干种走法,举例如下:

(0,1)->(1,1)->(1,2)->(2,2)->(3,2)->(3, 1),共花费5步

或者

(0,1)->(0, 0) -传送> (3,0)->(3,1),共花费3步 经检验3步是所需的最少步数,最后结果返回3。

1.2 输入描述

每一行输入都是用空格隔开的整数

第一行给出迷宫地图的长和宽,均为正整数

之后每一行的每一个数字,都代表迷宫的一格

-2表示起点,-3表示终点,-1表示不可通过的障碍物,0表示可通过的道路,大于0的正整数代表传送门,并且保证成对出现,在传送门上,可以仅用一步传送到另一一个相同数字的传送门]的位置。

1.3 输出描述

输出最少要多少步能够从起点走到终点。

输出-1如果没有任何办法从起点走到终点。

1.4 测试用例

1.4.1 input

4 3
1  0 -1  1
-2 0 -1 -3
2  2  0  0

1.4.2 output

3

1.5 代码示例 

def find_shortest_path(m):r = len(m)  # 行数c = len(m[0])  # 列数 迷宫第一行的长度# 将start和end的初始值设为Nonestart = Noneend = None# 遍历迷宫的每个位置,找到起点和终点的坐标for i in range(r):for j in range(c):if m[i][j] == -2:start = (i, j)elif m[i][j] == -3:end = (i, j)# 检查起点和终点是否成功找到,如果没有找到,则返回-1if not start or not end:return -1# 定义四个方向的移动,右移,左移,下移,上移directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]queue = [(start, 0)]  # 使用队列进行广度优先搜索  队列visited = {start}  # 记录已经访问过的位置  集合while queue:   # 队列不为空,执行循环current, steps = queue.pop(0)   # 取出队列中的第一个元素(current, steps),current表示当前格子坐标,steps表示到达当前格子所用的步数if current == end:  # 如果当前格子坐标等于终点坐标end,说明已经找到了最短路径,直接返回stepsreturn stepsfor direction in directions:  # 当前格子不是终点,则对当前格子的四个相邻格子进行遍历next_pos = (current[0] + direction[0], current[1] + direction[1])  # 当前位置的横坐标+direction的横坐标,当前位置的纵坐标+direction的纵坐标if 0 <= next_pos[0] < r and 0 <= next_pos[1] < c:  # 判断next_pos是否在迷宫范围内if m[next_pos[0]][next_pos[1]] != -1 and next_pos not in visited:  # 判断next_pos是否可以通过(障碍物)及是否已经被访问过queue.append((next_pos, steps + 1))  # 添加到队列,更新stepsvisited.add(next_pos)  # 添加到已访问集合中return -1# 读取迷宫地图
rows, cols = map(int, input("请输入迷宫地图的长和宽,以空格分隔:").split())  # 输入行数 列数,空格分隔,将分割后的字符串转换为整数,然后赋值给rows和cols.
maze = []  # 空列表,用于存储迷宫地图
for _ in range(rows):row = list(map(int, input("请输入迷宫每行的格子值,以空格分隔:").split()))  # 逐行读取迷宫地图maze.append(row)  # 将每一行添加到maze列表中# 计算最少步数
shortest_steps = find_shortest_path(maze)# 输出结果
print("最少要走的步数:", shortest_steps)

1.5.1 input

请输入迷宫地图的长和宽,以空格分隔:3 4
请输入迷宫每行的格子值,以空格分隔:1 0 -1 1
请输入迷宫每行的格子值,以空格分隔:-2 0 -1 -3
请输入迷宫每行的格子值,以空格分隔:2 2 0 0

1.5.2 output

最少要走的步数: 5

2 代码解释

2.1 current, steps = queue.pop(0)

这行代码从队列 queue 中取出第一个元素,并将其分解为 currentsteps 两个变量。队列是一种先进先出的数据结构,通过 pop(0) 操作可以取出队列中的第一个元素。在这里,current 表示当前所在的位置,steps 表示从起点到达当前位置所经过的步数。这样,我们可以在后续的操作中使用 currentsteps 来进行路径搜索和步数计算。

2.2 queue.append((next_pos, steps + 1)) 

queue.append((next_pos, steps + 1))
visited.add(next_pos)

在这段代码中,我们将下一个位置 next_pos 和当前步数 steps + 1 组成一个元组 (next_pos, steps + 1),并将其添加到队列 queue 中。这表示我们将继续以下一个位置为起点,步数加1的方式进行搜索。

同时,我们将下一个位置 next_pos 添加到集合 visited 中,表示该位置已经被访问过。这样可以避免重复访问同一个位置,以提高搜索效率。

通过以上操作,我们实现了广度优先搜索算法中的扩展操作,将下一个可行的位置加入队列,并标记为已访问。这样可以保证在搜索过程中不会遗漏任何可行的路径,并且不会陷入无限循环。

appendadd 是不同的方法,用于在不同的数据结构中添加元素。

  • append列表(List)对象的方法,用于在列表末尾添加一个元素。在上述代码中,我们使用 queue.append((next_pos, steps + 1)) 将一个元组添加到队列的末尾。

  • add集合(Set)对象的方法,用于向集合中添加一个元素。在上述代码中,我们使用 visited.add(next_pos) 将下一个位置添加到已访问的集合中。

两者的区别在于,append 是针对列表的操作,将元素添加到列表的末尾;而 add 是针对集合的操作,将元素添加到集合中


http://www.ppmy.cn/news/300030.html

相关文章

收音机调谐拉线维修

好久没更新博客了&#xff0c;因为实在是太忙啦~刚忙完搬家的事情&#xff0c;今天正好有空&#xff0c;就给大家来点干货。 事情是这样的&#xff0c;笔者手头有一个袖珍机械调谐收音机&#xff0c;型号为德生R1012&#xff0c;FM/MW/SW1-8/TV 12Bands收音机&#xff0c;虽然是…

一台老式收音机——飞乐牌251-1(交流电子管)

飞乐牌251-1收音机 (交流电子管) 它已经在我们家里无声无息地躺了二十多年了&#xff0c;记得我最后一次去拆它是高中毕业那年&#xff0c;之后再也没有去捣鼓过。前几年老妈嫌它占地方&#xff0c;扔前问我要不要收留这个劳什子&#xff0c;我如获至宝。但是我也只是让它换了个…

44、RDA5807收音机实验

文章目录 1、特点2、控制接口3、状态转换4、实验目的5、原理图6、代码实现1、特点 RDA5807 芯片研发而成的新一代数字调频收音机模块,主要应用于 MP3/MP4 媒体播放机,具有比传统模拟制式收音机模块更突出的性能表现,音质更清晰, 噪音极少,功耗更低,集成度高,对炬力、瑞芯…

乐歌升降桌怎么选,哪个型号比较好

随着时代的发展&#xff0c;人们坐在电脑桌前的时间越来越多&#xff0c;常常一天十几个小时一动不动&#xff0c;久而久之就必须要安排一台升降桌来辅助办公&#xff0c;不然颈椎、腰椎等身体部位真的受不了。 乐歌升降桌的型号其实不是很多&#xff0c;选购时尤其要注意的地…

kafka集群报错找不到broker

一、问题描述 某次用户反馈&#xff0c;kafka消费这边消息失败&#xff0c;报错消费者被踢出消费组或broker状态异常无法连接&#xff0c;后实际验证端口确实不通 现场测试验证&#xff0c;报错&#xff1a;报错&#xff1a;Failed to find brokers to send ListGroups……fi…

Git GitLab 使用及规范

Git 基本操作 Git安装配置及基本使用 从官网下载安装包&#xff0c;手动完成安装。打开Git Bash命令行工具&#xff0c;执行命令ssh-keygen -t rsa -C Email-Addresss生成一个密钥对。登录到GitLab&#xff0c;点击右上角你的用户头像&#xff0c;点击Edit Profile settings&…

iPhone手机使用:解决iPhone手机桌面APP图标,突然全部移动到居底部显示的问题(手机桌面图标不置顶显示)

昨天由于手残误点手机&#xff0c;不知道怎么回事&#xff0c;手机的APP图标本来是居顶部显示的&#xff0c;突然全部居底部显示&#xff0c;后来才知道原来是手指轻触home键造成的。 具体如图所示&#xff1a; 解决方式&#xff1a;直接把手指放到home键上轻点两下&#xff0…

手机图片设置桌面快捷方式

荣耀手机为例&#xff1a; 1、打开手机文件管理 2、找到需要设置的图片 3、右下角点击更多 4、设置桌面快捷方式 5、OK&#xff0c;这样在桌面即可打开核酸码了

华为手机怎么隐藏按键图标_华为手机如何隐藏桌面图标

手机桌面上有我们所有的软件和应用&#xff0c;特别是手机被人借走的时候&#xff0c;还担心自己的小秘密会别人发现&#xff01;这个时候你可能会选择把软件卸载掉&#xff0c;但是你还要在装回去&#xff0c;反反复复好麻烦啊&#xff01;现在不用怕啦&#xff01;有了这个功…

android 如何自定义桌面,安卓手机桌面设置教程 个性化你的桌面

Android系统是一款功能非常的强大的全球智能手机操作系统&#xff01;而相对于一些新手来说&#xff0c;熟练的操作安卓手机非常的难&#xff0c;那么下面我就安卓手机桌面设置来给新手用户一个简单的教程&#xff0c;让你的手机桌面变的更加的人性化&#xff01; 随着谷歌Adro…

华为手机左侧快捷方式,手机桌面太复杂?华为手机自动对齐整理桌面图标方法!...

和大多数网友一样&#xff0c;装机之家也是一个应用控&#xff0c;手机上装满了各种各样的应用&#xff0c;但日常生活中&#xff0c;除了微信、微博等使用频率较高的应用&#xff0c;其它应用的打开率基本为0。对此&#xff0c;每隔一段时间下来装机之家都会整理下手机桌面。诸…

鸿蒙系统图标大小怎么调节,华为手机桌面图标大小怎么调?用华为手机的朋友这些技巧需要了解...

以搭载EMUI11系统的华为mate40为例&#xff0c;桌面图标大小调整方法如下。首先需打开手机设置&#xff0c;选择“桌面与壁纸”模块进入&#xff1b;然后点击“桌面设置”&#xff0c;再选择“桌面布局”&#xff1b;最后选择对应的布局样式即可。华为手机布局样式有46、55、56…

关于手机APP在手机桌面图标圆形的,圆角方形的,直角方形的自动适配。

去年看到有人提了说桌面图标在有的手机上不一样&#xff0c;即使同一个手机不同的app&#xff0c;图标也是不一样&#xff0c;有的方形&#xff0c;有的圆形&#xff08;华为手机8.0&#xff09;&#xff0c;就自己网上看了看&#xff0c;把公司的app桌面图标适配了&#xff0c…

如何把手机计算机图标放到桌面,手机桌面图标怎么设置,桌面图标主题包

??现在几乎所有的大学生都配备一台电脑&#xff0c;但是有了电脑很容易&#xff0c;但是如果电脑上出现一了些问题&#xff0c;那我们应该怎么办呢?比如很多的的朋友会在电脑桌面上发现图标消失的情况&#xff0c;如果有重要的文件在桌面上&#xff0c;然后消失了就会遇到一…

android 手机桌面,安卓手机桌面介绍:教你认识安卓手机桌面

一个新手拿到手机&#xff0c;开机后看到的第一个画面就是桌面了&#xff0c;想要玩转整个手机&#xff0c;那么就先把桌面的各个功能都了解下吧。一般来说&#xff0c;刚买的新手机都是用的自带桌面&#xff0c;不同品牌的手机也是各不相同&#xff0c;但是功能方面都是大同小…

Android-动态修改APP桌面图标

背景 最近公司有个动态修改APP桌面图标的需求&#xff0c;需要做一下技术调研&#xff0c;网上查了一下实现方案&#xff0c;然后参考网上的方案写了个实现demo&#xff0c;在这里记录一下。 题外话&#xff1a;由于图标切换都是本地配置的&#xff0c;产品问了一句&#xff…

android桌面小工具,超好用的手机桌面小组件,一键美化桌面,实用又美观

原标题&#xff1a;超好用的手机桌面小组件&#xff0c;一键美化桌面&#xff0c;实用又美观 今日分享&#xff1a;安卓小组件 适用系统&#xff1a;安卓 小部件一直以来都是安卓手机中比较常见的功能&#xff0c;长按桌面就能添加小部件&#xff0c;从而轻松实现动态天气、代办…

android手机桌面图标消失解决方法

&#xfeff;&#xfeff; 百度经验:jingyan.baidu.com 我的手机有时会出现桌面部分图标突然神秘消失不见&#xff0c;但是软件还在。之前在网上搜索多次都没有找到有效的方法&#xff0c;只能重装软件。今天试着自己摸索了一下&#xff0c;居然解决了。佩服自己一小下&#xf…

解决华为手机Android系统10.0不能隐藏桌面图标问题,全网唯一

在Android系统10.0之后对应用隐藏图标做了严格的限制&#xff0c;Android官网的意思就是&#xff0c;除非是系统应用或者是不含Android四大组件并且没有申请任何权限的app才能隐藏图标。内心一阵独白&#xff1a;这特么的还不如直接说不让隐藏图标&#xff01; 作为Android开发…

手机桌面上的计算机怎么删除,怎样删除桌面图标?删除桌面图标方法教学

电脑的逐步普及使我们的生活便捷了许多&#xff0c;不仅在日常工作上帮了我们大忙&#xff0c;而且生活中也离不了它&#xff0c;虽然现在的智能手机的功能就已经十分齐全&#xff0c;但有些操作它还是无法完成&#xff0c;需要使用电脑。使用电脑时总有一些难以删除掉的图标使…