BZOJ 1514 1514: [POI2006]ZAB

题意: 给定一个网格图，其中有一些坏点，要求使起点到终点的路径上的所有点到离该点最近的坏点的最小距离距离最大，求这个最大值。 解析: 读完题显然分为两部分: 第一部分:预处理所有点到他最近的坏点的距离。 第二部分:二分最大距离bfs判定。 第二部分不用说吧？ 主要就是卡在第一部分。 我们考虑按照每列来计算每个点的dis距离(即到他最近的坏点的距离) 显然可以发现，对于该列来说，每一行都可能有一个到该列最近的点，并且我们发现，，如果某一行有两个坏点的话，假设分别为A，B，并且A到该列的距离最近，那么B显然不会对这一列的dis有任何影响。 所以我们显然可以在求之前预处理一下每一行的如果存在坏点的那个最近的坏点的坐标。 接下来，我们讨论坏点k,l，设我们要更新的点是(x,y) 如果k优于l，那么我们不妨列一下式子。

还深深埋在心底，要除去，怕是不能活命。