BFS刷题

P1332

import queue
n,m,a,b=map(int,input().split())
infection=[]
boss=[]
for i in range(a):
    a_ls=list(map(int,input().split()))
    infection.append(a_ls)
for i in range(b):
    b_ls=list(map(int,input().split()))
    boss.append(b_ls)


grid=[[-1 for _ in range(m)] for _ in range(n)]
dist=[[0 for _ in range(m)] for _ in range(n)]

dx=[1,-1,0,0]
dy=[0,0,1,-1]

q=queue.Queue()
for i in range(a):
    q.put([infection[i][0]-1,infection[i][1]-1])
    grid[infection[i][0]-1][infection[i][1]-1]=0
    dist[infection[i][0]-1][infection[i][1]-1]=1
while(not q.empty()):
    now = q.get()
    for i in range(4):
        a,b=now[0]+dx[i],now[1]+dy[i]
        if(a<0 or b<0 or a>n-1 or b>m-1):
            continue
        if(dist[a][b] != 0):
            continue
        grid[a][b]=grid[now[0]][now[1]]+1
        dist[a][b]=1
        q.put([a,b])

for x in boss:
    print(grid[x[0]-1][x[1]-1])

P1162

import queue
n=int(input())
grid=[[0 for _ in range(n+2)] for _ in range(n+2)]
moto=[]
for _ in range(n):
    moto.append(list(map(int,input().split())))
for i in range(n):
    for j in range(n):
        grid[i+1][j+1]=moto[i][j]
dist=[[0 for _ in range(n+2)] for _ in range(n+2)]

dx=[-1,0,1,0]
dy=[0,-1,0,1]

q=queue.Queue()
q.put([0,0])
q.put([0,n+1])
q.put([n+1,0])
q.put([n+1,n+1])

dist[0][0],dist[0][n+1],dist[n+1][0],dist[n+1][n+1]=1,1,1,1
# grid[0][0],grid[0][n+1],grid[n+1][0],grid[n+1][n+1]


while(not q.empty()):
    now = q.get()
    for i in range(4):
        a,b=now[0]+dx[i],now[1]+dy[i]
        if(a<0 or b<0 or a>n+1 or b>n+1):
            continue
        if(dist[a][b] != 0):
            continue
        if(grid[a][b] == 1):
            continue
        grid[a][b]=2
        dist[a][b]=1
        q.put([a,b])

for i in range(1,n+1):
    for j in range(1,n+1):
        moto[i-1][j-1]=grid[i][j]

while(not q.empty()):
    q.get()

new_dist=[[0 for _ in range(n)] for _ in range(n)]
q.put([0,0])
while(not q.empty()):
    now = q.get()
    if(moto[0][0]==2):
        moto[0][0]=0
    for i in range(4):
        a,b=now[0]+dx[i],now[1]+dy[i]
        if(a<0 or b<0 or a>n-1 or b>n-1):
            continue
        if(new_dist[a][b] != 0):
            continue
        if(moto[a][b] == 1):
            new_dist[a][b]=1
            q.put([a,b])
            continue
        if(moto[a][b]==2):
            moto[a][b]=0
            new_dist[a][b]=1
            q.put([a,b])
            continue
        if(moto[a][b]==0):
            moto[a][b]=2
            new_dist[a][b]=1
            q.put([a,b])
            continue
for x in moto:
    for i in range(n):
        print(x[i],end=" ")
    print()

P1443

import queue
n,m,x,y=map(int,input().split())

grid=[[-1 for _ in range(m)] for _ in range(n)]
dist=[[0 for _ in range(m)] for _ in range(n)]

dx=[1,1,-1,-1,2,2,-2,-2]
dy=[2,-2,2,-2,1,-1,1,-1]

def bfs(x,y):
    q=queue.Queue()
    q.put([x-1,y-1])
    grid[x-1][y-1]=0
    dist[x-1][y-1]=1
    while(not q.empty()):
        now = q.get()
        for i in range(8):
            a,b=now[0]+dx[i],now[1]+dy[i]
            if(a<0 or b<0 or a>n-1 or b>m-1):
                continue
            if(dist[a][b] != 0):
                continue
            grid[a][b]=grid[now[0]][now[1]]+1
            dist[a][b]=1
            q.put([a,b])
    return grid

ans=bfs(x,y)
step=0
for x in ans:
    for y in x:
        print(y,end="   ")
        step+=1
        if step%3==0:
            print()

P1746

import queue

n=int(input())
grid = [list(map(int, list(input().strip()))) for _ in range(n)]
x1,y1,x2,y2=map(int,input().split())
dist=[[0 for _ in range(n)] for _ in range(n)]
dx=[-1,0,1,0]
dy=[0,-1,0,1]
q=queue.Queue()
def bfs(x1,y1):
    q.put([x1-1,y1-1])
    while(not q.empty()):
        now=q.get()
        for i in range(4):
            a,b=now[0]+dx[i],now[1]+dy[i]
            if(a<0 or b<0 or a>n-1 or b>n-1):
                continue
            if(grid[a][b] >0):
                continue
            if(dist[a][b] >0):
                continue
            dist[a][b]=dist[now[0]][now[1]]+1
            if a==x2-1 and b==y2-1:
                return dist[a][b]
            q.put([a,b])
    return -1

print(bfs(x1,y1))

P1747

import queue
x1,y1=map(int,input().split())
x2,y2=map(int,input().split())

grid=[[-1 for _ in range(20)] for _ in range(20)]
dist=[[0 for _ in range(20)] for _ in range(20)]

dx=[1,1,-1,-1,2,2,-2,-2,2,2,-2,-2]
dy=[2,-2,2,-2,1,-1,1,-1,2,-2,2,-2]
q=queue.Queue()

def bfs(x,y):
    q.put([x-1,y-1])
    grid[x-1][y-1]=0
    dist[x-1][y-1]=1
    while(not q.empty()):
        now = q.get()
        for i in range(12):
            a,b=now[0]+dx[i],now[1]+dy[i]
            if(a<0 or b<0 or a>19 or b>19):
                continue
            if(dist[a][b] != 0):
                continue
            grid[a][b]=grid[now[0]][now[1]]+1
            dist[a][b]=1
            q.put([a,b])
    
    return grid

ans_1=bfs(x1,y1)
# ********
#  ————记得清空————
# ********
while(not q.empty()):
    q.get()
grid=[[-1 for _ in range(20)] for _ in range(20)]
dist=[[0 for _ in range(20)] for _ in range(20)]
ans_2=bfs(x2,y2)
print(ans_1[0][0])
print(ans_2[0][0])

P2895

import sys
from collections import deque

INF = 10**9
N = 305  # 网格范围足够大
# danger[i][j] 表示 (i,j) 从何时开始变为危险（若永远不危险，设为 INF）
danger = [[INF] * N for _ in range(N)]

m = int(input())
for _ in range(m):
    x, y, t = map(int, input().split())
    # 更新 (x,y) 及四邻域：若已有更早的危险时刻则取较小值
    for dx, dy in [(0,0), (1,0), (-1,0), (0,1), (0,-1)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < N and 0 <= ny < N:
            danger[nx][ny] = min(danger[nx][ny], t)

# dist 数组记录从 (0,0) 到达各点的时间（-1 表示未访问）
dist = [[-1] * N for _ in range(N)]
q = deque()

# 起点必须在 t=0 时安全
if danger[0][0] > 0:
    q.append((0, 0))
    dist[0][0] = 0

ans = -1
while q:
    x, y = q.popleft()
    # 如果该点永远安全，则找到了答案
    if danger[x][y] == INF:
        ans = dist[x][y]
        break
    # 四个方向移动
    for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < N and 0 <= ny < N and dist[nx][ny] == -1:
            nt = dist[x][y] + 1  # 下一时刻
            # 只有当移动后时刻小于该点变危险的时间，才能进入
            if nt < danger[nx][ny]:
                dist[nx][ny] = nt
                q.append((nx, ny))
                
print(ans)