Предполагая, что карта прямоугольная, вы можете перебрать все граничные точки и начать заливку, чтобы найти наиболее удаленную точку от начальной точки:
bestSolution = { start: (0,0), end: (0,0), distance: 0 };
for each point p on the border
flood-fill all points in the map to find the most distant point
if newDistance > bestSolution.distance
bestSolution = { p, distantP, newDistance }
end if
end loop
Полагаю, это будет в O(n^2). Если я не ошибаюсь, это (L+W) * 2 * (L*W) * 4, где L - длина, а W - ширина карты, (L+W) * 2 - количество пограничных точек по периметру, (L*W) - количество точек. и 4 - это предположение о том, что заливка будет проходить через точку максимум 4 раза (со всех сторон). Поскольку n эквивалентно количеству точек, это эквивалентно (L + W) * 8 * n, что должно быть лучше, чем O(n 2 ). (Если карта квадратная, порядок будет O(16n 1,5 ).)
Обновление: в соответствии с комментариями, поскольку карта представляет собой скорее лабиринт (чем тот, на котором я думал вначале с простыми препятствиями), вы можете сделать ту же логику выше, но проверяя все точки в карта (в отличие от точек на границе). Это должно быть порядка O(4n 2 ), что все еще лучше, чем у F-W и Dijkstra's.
Примечание: Заполнение потоком больше подходит для этой задачи, поскольку все вершины напрямую связаны только через 4 границы. Первый обход карты в ширину может дать результаты относительно быстро (всего за O(n)). Я предполагаю, что каждая точка может быть проверена в заливке от каждого из его 4 соседей, таким образом, коэффициент в формулах выше.
Обновление 2: Я благодарен за все положительные отзывы, которые я получил относительно этого алгоритма. Отдельное спасибо @Georg за его обзор .
P.S. Любые комментарии или исправления приветствуются.