The longest swim

A sailing club races dinghies on a flooded gravel pit. The safety officer wants one number for the notice board: the longest swim a capsized sailor might face.

The problem

The pit was surveyed as a rectangle of squares. A square holds 1 if it is shore — bank or island, anything a swimmer can stand on — and 0 if it is open water.

The club counts a swim in squares. A swimmer moves to a square sharing an edge, never through a corner, so the swim between two squares is rows apart plus columns apart. Every water square has a nearest shore; report the longest of those nearest swims.

No water means nothing to swim from; no shore, nothing to swim to. Report -1 for either.

Input. pit — a list of equal-length lists of 0 and 1.

Output. The longest swim to a nearest shore, in squares, or -1.

Example.

pit = [[0, 0, 0, 0, 1],
       [0, 0, 0, 0, 0],
       [1, 0, 0, 0, 0],
       [0, 0, 0, 0, 0]]   ->  4

Shore sits at the top-right corner and half-way down the west bank. Row 3, column 3 is four squares from either; every other square is within three of one of them.

A second example, where one island serves the whole pit:

pit = [[0, 0, 0, 0, 0],
       [0, 0, 1, 0, 0],
       [0, 0, 0, 0, 0]]   ->  3

All four corners are three squares out, and the last layer holds all four.

And a pit that is all water:

pit = [[0, 0],
       [0, 0]]   ->  -1

Constraints.

• 1 <= rows, cols <= 100
• every entry is 0 or 1

Hints

Approach

Brute force

For every water square, scan every shore square and keep the smallest row gap plus column gap; the answer is the largest of those minimums. With s shore squares and w water squares that is s · w comparisons — about 25 million on a 100 × 100 pit.

The insight

One breadth-first search seeded with every shore square at once labels each water square with its distance to the nearest shore, and the last layer the search reaches is the answer.

Breadth-first search from a set of sources behaves as if a single hidden source sat one step behind all of them: a square is reached on the layer equal to its distance from the closest source. That distance is the swim the club counts because every square is passable and every step costs one, so no shortest path bends round anything and the search distance is exactly row gap plus column gap.

Algorithm

1. Put every shore square into a queue with label 0; leave water unlabelled.
2. If the queue is empty, or already holds every square, return -1.
3. Take the front square. Each unlabelled edge-neighbour inside the pit gets a label one higher and is pushed.
4. Track the largest label handed out.
5. When the queue empties, that largest label is the longest swim.

Complexity

Time O(rows · cols) — each square is pushed at most once and looks at four neighbours. Space O(rows · cols) — the label grid and the queue.

Solution

"""The longest swim — one breadth-first search seeded from every shore square."""

from collections import deque


def solve(pit):
    rows, cols = len(pit), len(pit[0])
    swim = [[-1] * cols for _ in range(rows)]   # -1: not yet reached by the search
    wave = deque()
    for r in range(rows):
        for c in range(cols):
            if pit[r][c] == 1:
                swim[r][c] = 0
                wave.append((r, c))             # every shore square seeds the same wave

    if not wave or len(wave) == rows * cols:    # no shore to reach, or no water to leave
        return -1

    longest = 0
    while wave:
        # Invariant: the queue holds squares in non-decreasing swim order, and
        # every square already labelled carries its distance to the nearest shore.
        r, c = wave.popleft()
        longest = max(longest, swim[r][c])
        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 swim[nr][nc] == -1:
                swim[nr][nc] = swim[r][c] + 1   # first arrival is the shortest
                wave.append((nr, nc))
    return longest

TESTS = [
    (([[0, 0, 0, 0, 1],
       [0, 0, 0, 0, 0],
       [1, 0, 0, 0, 0],
       [0, 0, 0, 0, 0]],), 4),
    (([[0, 0, 0, 0, 0],
       [0, 0, 1, 0, 0],
       [0, 0, 0, 0, 0]],), 3),                   # one island, four corners tie
    (([[0, 0], [0, 0]],), -1),                    # all water
    (([[1, 1], [1, 1]],), -1),                    # all shore
    (([[0]],), -1),                               # single square, water
    (([[1]],), -1),                               # single square, shore
    (([[1, 0]],), 1),                             # smallest pit with a swim
    (([[1] + [0] * 99],), 99),                    # a 100-wide strip, shore at one end
    (([[0, 1, 0],
       [1, 0, 1],
       [0, 1, 0]],), 1),                          # every water square touches shore
]

Pitfalls

• Running a separate search from each shore square and keeping the minimum per water square. Correct, and s · rows · cols — on a pit that is mostly bank, the brute force again with a queue.
• Returning 0 for a pit with no water or no shore. An empty queue ends the search with the largest label still 0; so does a queue holding every square. Neither is a swim, so check both before searching.
• Stepping to the eight touching squares. Diagonal moves make the answer the larger of the two gaps rather than their sum: on the first example that reports 3 for a swim the club counts as 4.

Variants

• Blue mould on the bench — the same many-source search, asking instead whether every square is reached.
• Crossing the mudflats — one source, eight neighbours, and obstacles the path must bend round.