返回顶部
首页 > 资讯 > 后端开发 > Python >Python使用广度优先搜索遍历混乱地铁问题
  • 224
分享到

Python使用广度优先搜索遍历混乱地铁问题

Python混乱地铁广度优先搜索遍历混乱地铁 2023-05-14 20:05:21 224人浏览 安东尼

Python 官方文档:入门教程 => 点击学习

摘要

目录混乱地铁问题【问题描述】【输入形式】【输出形式】【样例输入】【样例输出】程序设计 总结 混乱地铁问题 【问题描述】 在某个城市中地铁网极度混乱。一条地铁线路上

混乱地铁问题

【问题描述】

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

【输入形式】

  • 第一行输入地铁站的个数
  • 第二行依次输入每个地铁站的数字,以空格隔开
  • 第三行输入地铁站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 0
print(BFS(lst1,lst2,start,end)) 

总结 

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


Queen.append()

while Queen:

    t=Queen.pop() 

    if ……

        Queen.append()

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

到此这篇关于python使用广度优先搜索遍历混乱地铁问题的文章就介绍到这了,更多相关Python广度优先搜索遍历混乱地铁内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

--结束END--

本文标题: Python使用广度优先搜索遍历混乱地铁问题

本文链接: https://lsjlt.com/news/204489.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

猜你喜欢
  • Python使用广度优先搜索遍历混乱地铁问题
    目录混乱地铁问题【问题描述】【输入形式】【输出形式】【样例输入】【样例输出】程序设计 总结 混乱地铁问题 【问题描述】 在某个城市中地铁网极度混乱。一条地铁线路上...
    99+
    2023-05-14
    Python混乱地铁 广度优先搜索遍历 混乱地铁
  • Python怎么使用广度优先搜索遍历混乱地铁
    这篇文章主要介绍“Python怎么使用广度优先搜索遍历混乱地铁”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“Python怎么使用广度优先搜索遍历混乱地铁”文章能帮助大家解决问题。混乱地铁问题【问题描...
    99+
    2023-07-05
  • Java利用广度优先搜索实现抓牛问题
    目录一、原问题链接二、输入和输出三、输入和输出样例四、代码五、测试一、原问题链接 http://poj.org/problemid=3278 二、输入和输出 1.输入 两个数,第1...
    99+
    2024-04-02
  • python迷宫问题深度优先遍历实例
    一、迷宫介绍 用python解迷宫问题,迷宫是一个二维列表,本次用深度优先解开迷宫问题。定义起点和终点,从一个位置到下一个位置只能通过向上或下或左或右,走一步来实现,从起点出发,如...
    99+
    2024-04-02
  • Java怎么利用广度优先搜索实现抓牛问题
    本篇内容介绍了“Java怎么利用广度优先搜索实现抓牛问题”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!一、原问题二、输入和输出输入两个数,第...
    99+
    2023-07-02
  • 怎么用Java深度优先遍历解决迷宫问题
    本文小编为大家详细介绍“怎么用Java深度优先遍历解决迷宫问题”,内容详细,步骤清晰,细节处理妥当,希望这篇“怎么用Java深度优先遍历解决迷宫问题”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。什么是深度优先什么...
    99+
    2023-06-29
  • 详解Java利用深度优先遍历解决迷宫问题
    目录什么是深度优先一个简单的例子程序实现什么是深度优先 什么是深度,即向下,深度优先,即向下优先,一口气走到底,走到底发现没路再往回走。 在算法实现上来讲,深度优先可以考虑是递归的代...
    99+
    2024-04-02
  • 求解三维装箱问题的启发式深度优先搜索算法(python)
    ⭐️ 问题描述 给定一个容器(其体积为 V V V) 和一系列待装载的箱子,容器和箱子的形状都是长方体。问题的目标是要确定一个可行的箱子放置方案使得在满...
    99+
    2023-09-07
    深度优先 python 算法
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作