How to create a distance matrix for multiple points?

Question

Python

I have an n by m matrix. I need to create a matrix whose elements are the Manhattan distance to the nearest given point.
For example:
I have given points ((0, 0), (4, 4), (2, 2)). And a 5 by 5 matrix.
Result:

I made a sketch that creates a separate distance matrix for each point and then takes smaller elements:

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)

But as is clear for large matrices and a large number of given points, it is inefficient.

Answer 1

Walk in width. First queue your starting points with distance 0 and mark those cells in some matrix as processed. Then, while the queue is not empty, take one cell out of it, look at 4 neighboring cells and, if they have not been processed yet, put them at the end of the queue with a distance of +1 to the current cell. Also, always mark cells as processed when placing them in the queue.
It will work O(nm) - no way faster.