What is left of the sheet

A stamp dealer buys part-used sheets by the block, not by the stamp. How many blocks does a torn sheet still hold?

The problem

A sheet of stamps is a rectangle of rows and columns, and stamps have been torn off it one at a time. Two survivors hang together if they share a perforated edge — above, below, left or right. Stamps that meet only at a corner are not joined: tweezers lift one without the other.

A block is a set of survivors that hang together, directly or through other survivors. A lone stamp is a block of one. Count the blocks.

Input. sheet — a list of rows, each a list of 1 (stamp still attached) and 0 (stamp torn off). Every row has the same length.

Output. The number of blocks.

Example.

sheet = [
  [1, 1, 0, 0, 1],
  [1, 0, 0, 1, 1],
  [0, 0, 1, 0, 0],
  [1, 0, 1, 0, 1],
]                       ->  5

Top-left three, top-right three, the pair in column 2 (its upper stamp touches the top-right block only at a corner), and a lone stamp in each bottom corner.

A second example, where the top row misleads:

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

The first two rows look like two separate columns. The bottom row joins them.

Constraints.

• 0 <= rows, cols <= 300
• every cell is 0 or 1
• an empty sheet has no rows

Hints

Approach

Brute force

Label every stamp with its own number, then sweep the sheet, rewriting the larger of two neighbouring labels as the smaller, until a sweep changes nothing. A label only moves one cell against the reading order per sweep, so a snake of stamps needs a sweep per cell of its backward runs, and each sweep touches every cell: O((rows · cols)²), about 8 · 10⁹ cell visits on a 300 × 300 sheet.

The insight

One flood fill started anywhere in a block discovers the whole block, so the number of blocks is the number of floods you have to start.

A flood from a stamp reaches exactly the stamps it hangs together with — neighbours, their neighbours, nothing across a gap. If it marks every cell it reaches, the scan can never start a second flood inside that block, so it starts one flood per block and counting the starts counts the blocks. The precondition is that "hangs together" runs both ways and chains, which is exactly how a block was defined.

Algorithm

1. Set blocks = 0; an empty sheet returns 0.
2. Scan every cell in reading order, skipping 0s.
3. On a 1, add one to blocks, set the cell to 0 and push it on a stack.
4. While the stack is not empty, pop a cell; for each of its four neighbours inside the sheet that is still 1, set it to 0 and push it.
5. When the stack empties, continue the scan. Return blocks at the end.

Complexity

Time O(rows · cols) — each cell is scanned once and pushed at most once, since it is set to 0 on the way in. Space O(rows · cols) worst case, for the stack under one solid block; the marking reuses the sheet.

Solution

"""What is left of the sheet — count blocks of 1s by flood fill."""


def lift_block(sheet, start_row, start_col):
    """Turn every stamp hanging together with (start_row, start_col) to 0."""
    rows, cols = len(sheet), len(sheet[0])
    stack = [(start_row, start_col)]
    sheet[start_row][start_col] = 0          # marked on push, so pushed once
    while stack:                             # invariant: every cell on the stack is 0 already
        r, c = stack.pop()
        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 sheet[nr][nc] == 1:
                sheet[nr][nc] = 0
                stack.append((nr, nc))


def solve(sheet):
    sheet = [row[:] for row in sheet]        # the caller keeps their sheet intact
    blocks = 0
    for r in range(len(sheet)):
        for c in range(len(sheet[r])):
            # invariant: every block that contains a cell before (r, c) in
            # reading order has been lifted, so a surviving 1 starts a new block
            if sheet[r][c] == 1:
                blocks += 1
                lift_block(sheet, r, c)
    return blocks

TESTS = [
    (([[1, 1, 0, 0, 1],
       [1, 0, 0, 1, 1],
       [0, 0, 1, 0, 0],
       [1, 0, 1, 0, 1]],), 5),
    (([[1, 0, 1],
       [1, 0, 1],
       [1, 1, 1]],), 1),
    (([],), 0),
    (([[1]],), 1),
    (([[0]],), 0),
    (([[1, 0, 1, 0, 1],
       [0, 1, 0, 1, 0],
       [1, 0, 1, 0, 1]],), 8),
    (([[1] * 300 for _ in range(300)],), 1),
    (([[0, 0, 0],
       [0, 0, 0]],), 0),
]

Pitfalls

• Marking a cell when it is popped instead of when it is pushed. On a full sheet a cell can go on the stack up to four times, about twice on average. The count survives; the stack size does not.
• Counting eight neighbours. Corner contact is not a join. With diagonals allowed, the first example gives 4, not 5.
• Forgetting the sheet edge. Row -1 is a legal Python index, so a flood at the top leaks into the bottom row. Check both bounds before touching a neighbour.

Variants

• Repainting the lido mosaic — the same flood, run once from a chosen cell instead of from every cell.
• Air pockets in the casting — the same count, but a block that reaches the border is disqualified.