Учитывая матрицу 1 и 0, где 0 представляет дома, а 1 представляет магазины, найдите квадрат минимального евклидова расстояния каждого дома до ближайшего магазина. Верните его как вектор вектора.
[[1, 1, 0],
[0, 0, 0],
[0, 0, 0]]
должен вернуть
[[0, 0, 1],
[1, 1, 2],
[4, 4, 5]]
Basi c BFS: (подход-1)
Если в матрице N элементов, для решения этой проблемы можно запустить BFS в каждом доме. Наихудшая сложность этого подхода заключается в следующем: наихудшее число BFS * O (E + V), где E - количество ребер в матрице, а V число узлов = N * O (N + 4N), поскольку число ребер равно постоянный фактор 4н. Временная сложность: O (N * N)
BFS с несколькими источниками (подход-2)
Инициализация очереди со всеми узлами (i , j) где i - номер строки, а j - столбец для всех магазинов. Для каждого узла (i, j) в очереди также сохраните свой соответствующий (si, sj) узел для хранилища, которое дает ему минимальный квадрат евклидова расстояния (назовите его sqDist). Для каждого узла магазина (i, j), (si, sj) будет таким же, как (i, j)
Инициализируйте ответ расстояния, который мы ищем для каждого дома, с -1
Во время BFS с несколькими источниками для узла (i, j) и его лучшего хранилища (si, sj) в очереди посмотрите на каждый из 8 смежных узлов (так как это евклидово расстояние, мы должны рассмотреть все 8 узлов, а не только 4 слева, справа, сверху, снизу). Если текущим значением расстояния для любого из этих узлов (nexti, nextj) является> sqDist, если (si, sj) выбрано в качестве лучшего хранилища для (nexti, nextj), тогда
- обновить расстояние из (nexti, nextj) с меньшим значением
- добавьте (nexti, nextj) вместе с лучшим хранилищем как (si, sj) в очередь
Продолжайте делать это, пока очередь не станет пустой
Мой вопрос:
1) почему это работает? Поскольку мы смотрим на евклидово расстояние, возможно, что (nexti, nextj) может быть не добавлено в очередь (или не обновлено их расстояние) для определенного (si, sj), но этот (si, sj) узел все еще может обновить расстояние для узлов, которые находятся дальше от него (nexti, nextj) из-за характера евклидова расстояния. Так что (si, sj), возможно, все еще должно быть в очереди. Как работает это решение, несмотря на эту проблему, или какова интуитивная концептуальная идея того, почему это работает, несмотря на эту проблему, поскольку она не очевидна?
2) Какова сложность времени?
кажется в В худшем случае вы можете добавить узел в очередь N раз. Таким образом, оно становится N * O (N * 4N), где 4N - количество ребер в матрице. Так не лучше ли делать BFS индивидуально для каждого дома?