Как создать матрицу расстояний для нескольких точек?

Question

[AkiroToshiro]

У меня есть матрица размером n на m. Мне нужно создать матрицу, элементами которой является манхеттенское расстояние к ближайшей данной точке.
К примеру:
У меня есть заданные точки ((0, 0), (4, 4), (2, 2)). И матрица размером 5 на 5.
Результат:
[[0 1 2 3 4]
[1 2 1 2 3]
[2 1 0 1 2]
[3 2 1 2 1]
[4 3 2 1 0]]
Я сделал набросок который создает отдельно матрицу расстояний для каждой точки а потом берет меньшие элементы:

x_size, y_size = 5, 5
x_arr, y_arr = np.mgrid[0:x_size, 0:y_size]
dists = []
cells = ((0, 0), (4, 4), (2, 2))
for cell in cells:
    dists.append(np.abs(x_arr - cell[0]) + np.abs(y_arr - cell[1]))
res = dists[0]
for i in range(1, len(dists)):
    res = np.minimum(res, dists[i])
print(res)

Но как понятно для для больших матриц и большего количества заданных точек он неэффективный.

Answer 1

[Wataru]

Обход в ширину. Сначала поместите в очередь ваши начальные точки с расстоянием 0 и пометьте эти клетки в какой-то матрице как обработанные. Потом, пока очередь не пуста, доставайте из нее одну клетку, смотрите 4 соседние клетки и, если они пока не обработаны, кладите их в конец очереди с расстоянием +1 к текущей клетке. Также всегда помечайте клетки обработанными когда помещаете их в очередь.

Работать это будет O(nm) - быстрее никак.