NFLSPC #2 火 题解

2019-11-28 22:51:14 By wzy

把第i行第j列的格子拆成aij个点(i,j,1),...,(i,j,aij) (i,j,k)表示第i行第j列的格子被已经烧了k秒的状态

考虑bfs

(i,j,k)向(i,j,k+1)连一条边(k < aij)

(i,j,aij)向四周连边((i-1,j,1)(i+1,j,1)(i,j-1,1)(i,j+1,1)如果目标点不存在不用连)

把所有初始被点燃的点一起放入队列bfs 最后一个被bfs到的点的时间就是答案(如果认为初始点时间是1) 时间复杂度o(n^2*a)

当然 因为时限很松 常数不大的dijkstra也可以通过此题

$by\ \text{skyline}$

评论

avatar
fgyg_zy
tql 用重载后的优先队列做,优先处理燃尽时间最先的

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。