bfs總結 bfs題單 最短路 python (奇怪的電梯 好奇怪的遊戲 迷宮 馬的周遊 [USACO08FEB]Meteor Shower S)

1 可以用來周遊所有的點
2 可以用來找最短路
3 多源最短路，開始時一次向隊列放之多個點

#闆子
"""
def bfs():
    1 起始點入隊
    标記入隊的點
    while not q.empty():
        出隊
        if 判斷是否到達終點 到達傳回
        for 周遊可走方向的點
            判斷目前點是否可行
            入隊
            标記
"""      

P1135 奇怪的電梯

https://www.luogu.com.cn/problem/P1135

import queue
n,a,b=map(int,input().split())
l=[0]+list(map(int,input().split()))
vis=[0]*(n+1)
def right(x):#判斷目前點是否合法
    if x>=1 and x<=n and vis[x]==0:
        return  True
    else:
        return False
q=queue.Queue()
def bfs(x):
    q.put((x,0))
    vis[x]=1
    while not q.empty():
        now=q.get()
        x=now[0]
        if now[0]==b:
            print(now[1])
            return#一定是return
        x1=x+l[x]
        x2=x-l[x]
        if right(x1):
            q.put((x1,now[1]+1))
            vis[x1]=1
        if right(x2):
            q.put((x2,now[1]+1))
            vis[x2]=1
    print(-1)#沒找到自動結束循環
bfs(a)
           

P1747 好奇怪的遊戲

https://www.luogu.com.cn/problem/P1747

兩次掉頭用bfs

from queue import Queue
a,b=map(int,input().split())
a1,b1=map(int,input().split())
vis= [[0] * (21) for i in range(21)]
#12個可走方向
dir=[(-1,2),(-2,2),(-2,1),(-1,-2),(-2,-1),(-2,-2),(2,1),(2,2),(1,2),(2,-2),(2,-1),(1,-2)]
def check(x,y):
    if x>=1 and x<=20 and y>=1 and y<=20 and vis[x][y]==0:
        return True
    return False
def bfs(x,y):#不同的搜尋，要開不同的隊列
    q = Queue()#一定要放在裡面
    q.put((x,y,0))
    vis[x][y]=1
    while not q.empty():
        now=q.get()
        x1=now[0]
        y1=now[1]
        step=now[2]
        if x1==1 and y1==1:
            print(step)
            return
        for l in dir:
            x2=x1+l[0]
            y2=y1+l[1]
            if check(x2,y2):
                q.put((x2,y2,step+1))
                vis[x2][y2]=1

bfs(a,b)
vis= [[0] * (21) for i in range(21)]#再次初始化
bfs(a1,b1)
           

P1605 迷宮

https://www.luogu.com.cn/problem/P1605

n,m,t=map(int,input().split())
a,b,a1,b1=map(int,input().split())
dir=[(0,1),(0,-1),(-1,0),(1,0)]
vis=[[0]*(m+2) for i in range(n+2)]
la=[[0]*(m+2) for i in range(n+2)]
for i in range(t):
    x,y=map(int,input().split())
    la[x][y]="1"
ans=0
def right(x,y):
    if x>=1 and y>=1 and x<=n and y<=m:
        return True
    return False
def dfs(x,y):
    global ans
    vis[x][y]=1
    if x==a1 and y==b1:
        ans=ans+1
        return
    for l in dir:
        x1=x+l[0]
        y1=y+l[1]
        if la[x1][y1]==0 and vis[x1][y1]==0 and right(x1,y1):
            dfs(x1,y1)
            vis[x1][y1]=0
dfs(a,b)
print(ans)
           

P1443 馬的周遊

https://www.luogu.com.cn/problem/P1443

import queue
n,m,x,y=map(int,input().split())
la=[[-1]*(m) for i in range(n)]#-1表示未通路過

dir=[(1,2),(2,1),(1,-2),(2,-1),(-1,-2),(-2,-1),(-1,2),(-2,1)]
def right(x,y):
    if x>=0 and y>=0 and x<n and y<m and la[x][y]==-1:
        return True
    else:
        return False
q=queue.Queue()
def bfs(x,y):
    q.put((x-1,y-1,0))
    la[x-1][y-1]=0
    while not q.empty():
        now=q.get()
        x1=now[0]
        y1=now[1]
        step=now[2]
        for l in dir:
            x2=x1+l[0]
            y2=y1+l[1]
            if right(x2,y2):
                q.put((x2,y2,step+1))
                la[x2][y2]=step+1
bfs(x,y)
for i in range(n):
    for j in range(m):
        print("{: <5d}".format(la[i][j]),end="")
    print()
           

P2895 [USACO08FEB]Meteor Shower S

https://www.luogu.com.cn/problem/P2895

import queue
m=int(input())
vis=[[0]*(303) for i in range(303)]#是否被通路過
la=[[-1]*(303) for j in range(303)]#流星标記位置
dir1=[(-1,0),(1,0),(0,1),(0,-1),(0,0)]
dir=[(-1,0),(1,0),(0,1),(0,-1)]
def right(x,y):
    if x>=0 and y>=0 and x<=301 and y<=301:
        return True
    else:
        return False
def right2(x,y):
    if x>=0 and y>=0 and vis[x][y]==0:
        return True
    else:
        return False
for i in range(m):
    a,b,t=map(int,input().split())

    for l in dir1:
        x1=a+l[0]
        y1=b+l[1]
        if right(x1,y1) and (la[x1][y1]==-1 or t<la[x1][y1]):
            la[x1][y1]=t
q=queue.Queue()
def bfs(x,y):
    q.put((x,y,0))
    vis[x][y]=1
    while not q.empty():
        now=q.get()
        x1=now[0]
        y1=now[1]
        s=now[2]
        if la[x1][y1]==-1:#若到達一個安全位置
            print(s)
            return
        for l in dir:
            x2=x1+l[0]
            y2=y1+l[1]
            if right2(x2,y2) and (s+1<la[x2][y2] or la[x2][y2]==-1):#位置合法且流星還未落下或該地方不會落流星
                q.put((x2,y2,s+1))
                vis[x2][y2]=1

    print(-1)
bfs(0,0)
#要考慮的細節較多