Cara menggunakan carian pertama luas dalam Python untuk merentasi kereta api bawah tanah yang huru-hara

Masalah kereta api bawah tanah huru-hara

[Penerangan masalah]

Rangkaian kereta api bawah tanah di bandar tertentu sangat huru-hara. Terdapat n stesen kereta api bawah tanah di laluan kereta api bawah tanah, bernombor 1 hingga n. Terdapat perhentian kereta api bawah tanah di setiap stesen di laluan kereta api bawah tanah Terdapat nombor m pada setiap stesen kereta api bawah tanah, yang mewakili bilangan perhentian yang mesti diambil oleh penumpang dari stesen ini. Setiap stesen metro mempunyai laluan metro yang menuju ke kedua-dua arah. Oleh itu, anda boleh memajukan stesen m ke arah dengan bilangan yang lebih besar, atau anda boleh memajukan stesen m ke arah dengan nombor yang lebih kecil. Walau bagaimanapun, jika anda melampaui skop stesen kereta api bawah tanah, anda tidak boleh menaiki kereta bawah tanah. Sebagai contoh, nombor di kereta bawah tanah bernombor 1 ialah 3. Jika anda menaiki kereta api di stesen kereta api bawah tanah itu, anda boleh duduk di arah hadapan ke stesen kereta api bawah tanah No. Tetapi anda tidak boleh menaiki bas ke arah bertentangan ke stesen kereta api bawah tanah -2, kerana stesen kereta api bawah tanah -2 tidak wujud. Sekarang seorang penumpang bermula dari stesen kereta api bawah tanah A dan ingin sampai ke stesen kereta api bawah tanah B. Bolehkah dia sampai ke kereta bawah tanah itu sekurang-kurangnya?

[Borang input]

• Masukkan bilangan stesen kereta api bawah tanah di baris pertama

• Barisan kedua mengikut turutan Masukkan nombor setiap stesen kereta api bawah tanah, dipisahkan dengan ruang

• Dalam baris ketiga, masukkan stesen kereta api bawah tanah A dan B, dipisahkan oleh ruang

[Format output]

Bilangan minimum perjalanan kereta api bawah tanah dari stesen kereta api bawah tanah A hingga B

[Sampel input]

5

2 4 1 2 3

1 2

[Sampel output]

2

Pengaturcaraan

Ringkasan

Keluasan carian pertama dilaksanakan terutamanya melalui baris gilir Format khusus ialah:

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))

Mula-mula masukkan elemen pertama ke dalam baris gilir, dan kemudian letakkan elemen pertama Ambilnya. keluar dan cari semua elemen undang-undang dan masukkannya ke dalam baris gilir, dan kemudian keluarkan mereka dari baris gilir satu demi satu sehingga baris gilir kosong, yang bermaksud bahawa semua elemen undang-undang telah dilalui.

Atas ialah kandungan terperinci Cara menggunakan carian pertama luas dalam Python untuk merentasi kereta api bawah tanah yang huru-hara. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!