寻找到水的最短距离
Finding shortest distance to water
我有一张陆地和水域的二维地图，如下图（l代表陆地，w代表水域）。
lllwwwlll
lllwllllw
lllllllww
lllllllll
对于每个陆地板块，我想知道它与最近的水域板块的距离。水平移动、垂直移动、对角移动都算一个距离。
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
这种方法可行，但速度很慢，尤其是当水砖很少时。
是否有更快的算法来计算每个地块与水的距离？
对地图中的所有图块执行 breadth-first-search，从水图块作为根开始，然后沿着边缘到相邻图块。您找到瓷砖的高度将是它与水的距离。
查看此答案以了解在 BFS 期间跟踪深度的好方法：
我们可以做类似下面的事情（类似于 BFS，但可能从多个源开始）：
队列 (FIFO) 最初是空的。有另一个 mxn 距离网格 D，所有元素都初始化为无穷大。
- 遍历所有方块并将水方块（的位置）推入队列（如果网格是 mxn，这将花费 O(mn)）。此外，对于所有水砖位置，D[pos] <- 0。
- 当队列不为空时，执行以下操作：
2.1.从队列中弹出一个方块 t。
2.2.检查所有相邻的图块t_a（左，右，上，下，对角线，也考虑角点情况，应该在O（1）时间内找到），并检查是否D[t_a] > D[t] + 1 然后 D[t_a] <- D[t] + 1 并将 t_a 推入队列。
mxn 网格的第 2 步不应超过 O(mn) 时间。
我有一张陆地和水域的二维地图，如下图（l代表陆地，w代表水域）。
lllwwwlll
lllwllllw
lllllllww
lllllllll
对于每个陆地板块，我想知道它与最近的水域板块的距离。水平移动、垂直移动、对角移动都算一个距离。
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
这种方法可行，但速度很慢，尤其是当水砖很少时。
是否有更快的算法来计算每个地块与水的距离？
对地图中的所有图块执行 breadth-first-search，从水图块作为根开始，然后沿着边缘到相邻图块。您找到瓷砖的高度将是它与水的距离。
查看此答案以了解在 BFS 期间跟踪深度的好方法：
我们可以做类似下面的事情（类似于 BFS，但可能从多个源开始）：
队列 (FIFO) 最初是空的。有另一个 mxn 距离网格 D，所有元素都初始化为无穷大。
- 遍历所有方块并将水方块（的位置）推入队列（如果网格是 mxn，这将花费 O(mn)）。此外，对于所有水砖位置，D[pos] <- 0。
- 当队列不为空时，执行以下操作： 2.1.从队列中弹出一个方块 t。 2.2.检查所有相邻的图块t_a（左，右，上，下，对角线，也考虑角点情况，应该在O（1）时间内找到），并检查是否D[t_a] > D[t] + 1 然后 D[t_a] <- D[t] + 1 并将 t_a 推入队列。
mxn 网格的第 2 步不应超过 O(mn) 时间。