【蓝桥杯】4535勇闯魔堡（多源BFS + 二分）

思路

k有一个范围（0到怪物攻击的最大值），求满足要求的k的最小值。很明显的二分套路。
关键是check函数怎么写，我们需要找到一条从第一行到最后一行的路径，每一次可以从上下左右四个方向前进，那么我么可以用BFS来查找是否存在。
这里还有一个思维上的关键点，在开始时我们可以随机选一个点出发，如果我们用遍历第一行满足要求的格子，用bfs依次判断，那么这题样例只能过60%。实际上只需把所有满足要求的格子都加入到deque，用多源dfs来一次性查找路径，才能通过所有样例。

code

用遍历第一行的写法只能通过60%的测试点，用多源bfs可以省去遍历的时间复杂度。
二分查找+普通BFS（测试样例通过12/20）：

import os
import sys
from collections import dequedef BFS(x,y,k):q = deque()q.append((x,y))vis = [[0 for i in range(m+1)] for j in range(n+1)]vis[x][y] = 1while len(q)!=0:x,y = q.popleft()if x == n:return Truefor dx,dy in [(-1,0),(1,0),(0,1),(0,-1)]:nx,ny = x+dx,y+dyif 1<=nx<=n and 1<=ny<=m and vis[nx][ny]==0:if a[nx][ny] > k:continueq.append((nx,ny))vis[nx][ny] = 1return Falsedef check(k):flag = Falsefor i in range(1,m+1):if a[1][i]>k:continueif BFS(1,i,k):flag = Truereturn flagglobal n,m
n,m = map(int, input().split())
a = [[0 for i in range(m+1)]]
for _ in range(n):a.append([0]+list(map(int,input().split())))l,r = 0,1001
ans = 0
while l<=r:mid = (l+r)//2if check(mid):ans = midr = mid-1else:l = mid+1
print(ans)

二分查找+多源BFS（测试样例通过20/20）：

import os
import sys
from collections import dequedef BFS(q,vis,k):while len(q)!=0:x,y = q.popleft()if x == n:return Truefor dx,dy in [(-1,0),(1,0),(0,1),(0,-1)]:nx,ny = x+dx,y+dyif 1<=nx<=n and 1<=ny<=m and vis[nx][ny]==0:if a[nx][ny] > k:continueq.append((nx,ny))vis[nx][ny] = 1return Falsedef check(k):q = deque()vis = [[0 for i in range(m+1)] for j in range(n+1)]for j in range(1,m+1):if a[1][j]<=k:q.append((1,j))vis[1][j] = 1return BFS(q,vis,k)global n,m
n,m = map(int, input().split())
a = [[0 for i in range(m+1)]]
for _ in range(n):a.append([0]+list(map(int,input().split())))l,r = 0,1001
ans = 0
while l<=r:mid = (l+r)//2if check(mid):ans = midr = mid-1else:l = mid+1
print(ans)