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

WBOY
发布: 2023-04-28 08:01:13
转载
1560人浏览过

    混乱地铁问题

    【问题描述】

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

    【输入形式】

    • 第一行输入地铁站的个数

    • 第二行依次输入每个地铁站的数字,以空格隔开

    • 第三行输入地铁站A和B,以空格隔开

    【输出形式】

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

    【样例输入】

    5

    立即学习Python免费学习笔记(深入)”;

    2 4 1 2 3

    纳米搜索
    纳米搜索

    纳米搜索:360推出的新一代AI搜索引擎

    纳米搜索 30
    查看详情 纳米搜索

    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 0
    print(BFS(lst1,lst2,start,end))
    登录后复制

    总结 

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

    Queen.append()
    
    while Queen:
    
        t=Queen.pop() 
    
        if ……
    
            Queen.append()
    登录后复制

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

    以上就是Python怎么使用广度优先搜索遍历混乱地铁的详细内容,更多请关注php中文网其它相关文章!

    相关标签:
    python速学教程(入门到精通)
    python速学教程(入门到精通)

    python怎么学习?python怎么入门?python在哪学?python怎么学才快?不用担心,这里为大家提供了python速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

    下载
    来源:亿速云网
    本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
    最新问题
    开源免费商场系统广告
    热门教程
    更多>
    最新下载
    更多>
    网站特效
    网站源码
    网站素材
    前端模板
    关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新 English
    php中文网:公益在线php培训,帮助PHP学习者快速成长!
    关注服务号 技术交流群
    PHP中文网订阅号
    每天精选资源文章推送
    PHP中文网APP
    随时随地碎片化学习

    Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号