Алгоритм поиска электростанции на 2-й сетки
Как показывает изображения, есть 2d сетки с домов и PowerStations. Выясните алгоритм поиска ближайшей электростанции для каждого дома. Я знаю, как написать грубую силу со сложностью O (m * n), в которой m - количество домов, а n - количество электростанций. Но может ли кто-нибудь дать лучшее решение? (Можно предположить, что электростанции регулярно расположены таким образом)
Если ваш вход является сеткой, выполните BFS.
Сначала вставьте в очередь все электростанции. Затем выполните BFS, как обычно, с одной небольшой модификацией: вы должны помнить, с какой начальной электростанции был добавлен каждый добавленный квадрат.
Используя этот алгоритм, вы, естественно, достигнете каждого дома с ближайшей электростанцией.
Сложность O(s^2). Где s - сторона сетки.
Ввод - это один список домов с координатами и другой список электростанций с координатами. Это что-то вроде {home: [[1, 2], [2, 3], [3, 4]]}, {PS: [[2, 2], [2,7]]} – Wizard
Мне интересен алгоритм O (m * n) грубой силы (кажется, не хватает какого-то фактора). Один (теоретический, возможно, не практический) подход: используйте Флойд-Варшалл для вычисления кратчайших путей O (V^3) всех пар и ищите решение в O (m * n) времени. – sascha