algorithm - 寻找到水的最短距离

Question

我有一个陆地和水域的二维 map ，如下所示(l 代表陆地，w 代表水域)。

lllwwwlll
lllwllllw
lllllllww
lllllllll

对于每个地 block ，我想知道它与最近的水域地 block 的距离。水平、垂直和对角线移动都算作一个距离。

321www111
321w1111w
3211121ww
322222111

现在我正在使用这样的算法:

foreach tile in map
  if isWater(tile)
    tile.distanceFromWater = 0
  else
    radius = 1
    while !hasWaterAround(tile, radius)
      radius++
    tile.distanceFromWater = radius

这种方法有效，但速度相当慢，尤其是当水砖很少时。

是否有更快的算法来计算每个地 block 与水的距离？

Answer 1

我们可以做类似下面的事情(类似于 BFS，但可能从多个源开始):

队列 (FIFO) 最初是空的。有另一个 mxn 距离网格 D，所有元素都初始化为无穷大。

1. 遍历所有方 block 并将水方 block (的位置)插入队列(如果网格是 mxn，这将花费 O(mn))。此外，对于所有水砖位置，D[pos] <- 0。
2. 当队列不为空时，执行以下操作:2.1.从队列中弹出一个方 block t。2.2.检查所有相邻的瓦片 t_a(左、右、上、下、对角线，也考虑角点情况，应该在 O(1) 时间内找到)，并检查是否 D[t_a] > D[t] + 1 then D[t_a] <- D[t] + 1 并将 t_a 插入队列。

对于 mxn 网格，第 2 步的时间不应超过 O(mn)。