尋找與水的最短距離

我有一幅土地和水的二維地圖，如下所示（l代表土地和w代表水）。尋找與水的最短距離

lllwwwlll 
lllwllllw 
lllllllww 
lllllllll

對於每塊地塊，我想知道它與最近的水瓦的距離。水平移動，垂直移動和對角移動均可計爲一個距離。

現在我使用的是算法，像這樣：

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

這種方法的工作原理，但它比較慢，尤其是當有很少的水磚。

是否有更快的算法來查找每個地塊與水的距離？

來源

2017-01-31 Peter Olson

檢查A *方法[wiki]（https://en.wikipedia.org/wiki/A*_search_algorithm） – fl00r

我們可以做類似如下（類似於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推入隊列。

步驟2對於mxn網格的時間不應超過O（mn）個時間。

來源

2017-01-31 17:50:50

Upvoted，但步驟2可以更簡單，我認爲。我們只需要檢查D [t_a]是否無窮大 - 保證給定算法的BFS性質，第一次分配到距離將是最小的。 –

是的，但即使在這種情況下，我們需要if塊（檢查！=無窮大而不是當前的檢查），所以從時間複雜度來看，它將保持相同的我猜。 –

是的，但它使理解算法變得更簡單，因爲按照書面的說法，每個D可以更新多次。 –

對地圖中的所有拼貼進行寬度優先搜索，以水磚作爲根，並將邊緣跟隨到相鄰拼貼。你發現瓷磚的水平將是它與水的距離。

看到這個答案的一個很好的方法來跟蹤深度BFS期間：

How to keep track of BFS depth in C++

來源

2017-01-31 17:46:51

尋找與水的最短距離

回答

相關問題