The nearest standpipe

Visitors carry water from the nearest standpipe, and the groundsman wants the number of paces painted on every plot marker. Do not search from each plot — search from the taps.

The problem

A cemetery is a rectangular grid of plots with a gravel walk between every row and column. One pace takes a visitor to the plot directly north, south, east or west, never diagonally, and any plot can be walked past. A few positions hold a standpipe instead of a grave.

plots[r][c] is 0 where a standpipe stands and 1 where a plot lies. For every position, find the paces to the nearest standpipe. A standpipe is 0 paces from itself.

Input. plots — a list of equal-length lists of 0 and 1, with at least one 0.

Output. A grid of the same shape: the fewest paces from each position to any standpipe.

Example.

plots = [[1, 1, 1, 0],
         [1, 1, 1, 1],
         [0, 1, 1, 1],
         [1, 1, 1, 1]]

->      [[2, 2, 1, 0],
         [1, 2, 2, 1],
         [0, 1, 2, 2],
         [1, 2, 3, 3]]

The top-left plot is 3 paces from the corner tap but 2 from the one on the west edge, so it gets 2.

A second example, one tap in a two-row strip:

plots = [[1, 1, 1, 1, 1],
         [1, 1, 0, 1, 1]]

->      [[3, 2, 1, 2, 3],
         [2, 1, 0, 1, 2]]

Every number is row gap plus column gap; nothing forces a detour.

Constraints.

• 1 <= rows, cols <= 10^4
• 1 <= rows * cols <= 10^5
• plots[r][c] is 0 or 1, and at least one is 0

Hints

Approach

Brute force

For every plot, look at every standpipe and keep the smallest row gap plus column gap. With p plots and t taps that is p · t comparisons; p + t is at most 10⁵, so p · t can reach 2.5 × 10⁹. A separate search from each plot is no better: each can cross the whole grid before it meets a tap.

The insight

Run one breadth-first search that begins at every standpipe at the same time; the layer in which a plot is first reached is its distance to the nearest tap.

Breadth-first search hands out distances in non-decreasing order, because the queue always holds a run of cells at distance d followed by a run at d + 1. Seeding it with every tap at 0 is the same as adding an imaginary well joined to each tap by a zero-length pipe and searching from the well, so the first arrival at a plot came through its nearest tap. The precondition is that every pace costs the same — a plain queue only finds shortest paths when all edges weigh one — and here it does.

Algorithm

1. Build paces, a grid the shape of plots filled with -1 (not yet reached).
2. For every standpipe, set paces[r][c] = 0 and append (r, c) to a queue.
3. Pop the front. For each of its four neighbours inside the grid that still holds -1, set its paces to the popped cell's paces plus one, and append it.
4. When the queue empties, return paces.

Complexity

Time O(rows · cols) — each position enters the queue once and inspects four neighbours. Space O(rows · cols) — the answer grid and the queue.

Solution

"""The nearest standpipe — breadth-first search seeded from every tap at once."""

from collections import deque


def solve(plots):
    rows, cols = len(plots), len(plots[0])
    paces = [[-1] * cols for _ in range(rows)]   # -1: not yet reached
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if plots[r][c] == 0:
                paces[r][c] = 0
                queue.append((r, c))              # every tap seeds the same search

    while queue:
        # Invariant: every cell in the queue already holds its final distance,
        # and the queue reads as a run of some distance d followed by a run of
        # d + 1, so the first cell to reach a plot came from its nearest tap.
        r, c = queue.popleft()
        for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
            if 0 <= nr < rows and 0 <= nc < cols and paces[nr][nc] == -1:
                paces[nr][nc] = paces[r][c] + 1
                queue.append((nr, nc))
    return paces

TESTS = [
    (([[1, 1, 1, 0],
       [1, 1, 1, 1],
       [0, 1, 1, 1],
       [1, 1, 1, 1]],),
     [[2, 2, 1, 0],
      [1, 2, 2, 1],
      [0, 1, 2, 2],
      [1, 2, 3, 3]]),
    (([[1, 1, 1, 1, 1],
       [1, 1, 0, 1, 1]],),
     [[3, 2, 1, 2, 3],
      [2, 1, 0, 1, 2]]),
    (([[0]],), [[0]]),                                   # a lone tap
    (([[0, 0], [0, 0]],), [[0, 0], [0, 0]]),             # every position is a tap
    (([[0, 1, 1, 1, 1, 1, 1]],), [[0, 1, 2, 3, 4, 5, 6]]),  # one row, tap at the end
    (([[1], [1], [0]],), [[2], [1], [0]]),               # one column, tap at the bottom
    (([[1, 1, 1],
       [1, 0, 1],
       [1, 1, 1]],),
     [[2, 1, 2],
      [1, 0, 1],
      [2, 1, 2]]),                                       # corners sit two paces out
]

Pitfalls

• Setting the distance at pop time rather than push time. A plot can then be pushed by all four neighbours before its first pop, and the queue grows to several times the grid. The numbers are right; the memory is not.
• Reusing plots as the answer grid. A plot holds 1, and so does a plot 1 pace from a tap; the search cannot tell them apart and stops early. Keep a separate grid filled with -1, a value no distance can take.
• Popping from the front of a plain list. pop(0) shifts every element, so 10⁵ positions cost 10¹⁰ moves. Use collections.deque.

Variants

• Blue mould on the bench — the same search from every source at once, asking only for the layer count.
• Crossing the mudflats — one source, eight neighbours, and squares that cannot be stood on.