【蓝桥杯】12111暖气冰场（多源BFS 或者 二分）
思路
这题可以用BFS做，也可以用二分来做。
用二分这里只提供一个思路：对时间来二分查找，check函数就是检查在特定的时间
t
0
t_0
t0内每一个暖气炉的传播距离能否覆盖所有格子。
用BFS做：
由几个点开始向外扩散，知道铺满整个面。可以用BFS来做，原本的BFS是从一个点开始加入deque，多源BFS那现在就先把所有的暖气炉加入deque，再遍历就行了。
还有一个注意点，题目的输出是花了多少时间，也就是扩散的轮数，我们可以用距离来度量时间，一秒钟一格，所以我们时刻更新所出现的距离暖气炉最远的距离即可。我们把vis标记数组替换为dis数组 兼具判断是否遍历和记录距离的作用。
code
import os
import sys
from collections import deque
n,m,t = map(int,input().split())
q = deque()
dis = [[-1 for i in range(m+1)] for j in range(n+1)]
for i in range(t):
x,y = map(int,input().split())
q.append([x,y])
dis[x][y] = 0
ans = 0
while len(q)!=0:
x,y = q.popleft()
for dx,dy in [(-1,0),(+1,0),(0,-1),(0,+1),(-1,-1),(-1,+1),(+1,-1),(+1,+1)]:
nx,ny = x+dx,y+dy
if 1<=nx<=n and 1<=ny<=m:
if dis[nx][ny]==-1:
q.append([nx,ny])
dis[nx][ny] = dis[x][y] + 1
ans = max(ans,dis[nx][ny])
print(ans)
原文地址:https://blog.csdn.net/2301_77168269/article/details/146448138
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.kler.cn/a/597269.html 如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.kler.cn/a/597269.html 如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！