把第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}$