文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Python怎么使用广度优先搜索遍历混乱地铁

2023-07-05 22:33

关注

这篇文章主要介绍“Python怎么使用广度优先搜索遍历混乱地铁”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“Python怎么使用广度优先搜索遍历混乱地铁”文章能帮助大家解决问题。

混乱地铁问题

【问题描述】

在某个城市中地铁网极度混乱。一条地铁线路上有n个地铁站,分别编号为1到n。地铁线路上的每一个站都会停靠地铁,每一个地铁站上都有一个数字m,代表从此站出发乘客必须乘坐的站数。每个地铁站都有通往两个方向的地铁。因此可以向编号大的方向前进m站,也可以向编号小的方向前进m站。但如果前进后超出了地铁站的范围,则该地铁不可被乘坐。例如编号为1的地铁上的数字为3,那么在该地铁站上车,可以向正方向坐到4号地铁站。但不能反方向坐车到-2号地铁站,因为-2号地铁站不存在。现在乘客从A号地铁站出发,想要到达B号地铁站,求他能否到达,最少要搭乘多少次地铁?

【输入形式】

【输出形式】

地铁站A到B最少要搭乘地铁的次数

【样例输入】

5

2 4 1 2 3

1 2 

【样例输出】

2

程序设计 

n=int(input())lst1=[int(i) for i in range(n)]lst2=list(map(int,input().split()))start,end=map(int,input().split())def BFS(lst1,lst2,start,end):      #广度优先搜索遍历    count=0          #计算达到终点所需乘坐地铁的次数    visited=[0 for i in range(n)]    #设置标志列表    Queue=[]         #设置队列,用于广度优先搜索遍历    Queue.append(start-1)   #将起点放入队列    flag=1           #用于改变方向    while Queue:    #开始循环遍历        t=Queue.pop(0)   #出队        for i in range(2):    #分别向左右两个方向走            flag=-1*flag    #改变方向                   new=lst1[t]+flag*lst2[t]    #到达的新的地铁站的下标            if new<0 or new>=n:      #检查是否合法                continue             if new>=0 or new<n:                Queue.append(new)     #若合法,就放入队列中                visited[new]=1        #标记一下                count+=1              #乘坐的地铁次数                if visited[end-1]==1:   #如果终点被标记了,说明已经到终点了                    return count    return 0print(BFS(lst1,lst2,start,end))

总结 

广度优先搜索遍历主要通过一个队列来实现,具体的格式为:

Queen.append()while Queen:    t=Queen.pop()     if ……        Queen.append()

先将第一个元素放入队列中,然后将第一个元素取出,并找到合法的所有元素放入队列中,再挨个从队列中取出,直到队列为空,表示所有合法的元素都已经被遍历过了。

关于“Python怎么使用广度优先搜索遍历混乱地铁”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识,可以关注编程网行业资讯频道,小编每天都会为大家更新不同的知识点。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯