Нахождение кратчайшего расстояния до воды

У меня есть двумерная карта земли и воды, как и следующая (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) изначально пустую. Иметь еще одну сетку dx xxn расстояний со всеми элементами, инициализированными до бесконечности.

Пройдите все плитки и нажмите (положение) плитки воды в очереди (это займет O (mn), если сетка равна mxn). Кроме того, 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 не должен занимать больше времени O (mn) для сетки mxn.

источник

2017-01-31 17:50:50

Упрощенный, но шаг 2 может быть проще, я думаю. Нужно только проверить, является ли D [t_a] бесконечностью - это гарантировано, учитывая природу BFS алгоритма, что первое присваивание на расстояние будет наименьшим. –

Да, но даже в этом случае нам нужен блок if (проверьте if! = Бесконечность вместо текущей проверки), поэтому с точки зрения временной сложности он останется тем же, что и я. –

Да, но это упрощает понимание алгоритма, поскольку, как написано, кажется, что каждый D может обновляться несколько раз. –

Сделайте первый поиск по всем плиткам на карте, начиная с плитки воды в виде корней и следующих краев соседних плит. Уровень, на котором вы найдете плитку, будет расстоянием от воды.

Смотрите этот ответ на хороший способ отслеживать глубину во BFS:

How to keep track of BFS depth in C++

источник

2017-01-31 17:46:51

Нахождение кратчайшего расстояния до воды

ответ

Смежные вопросы