Repainting the lido mosaic

An open-air lido is relaying the mosaic round its pool. The tiler recolours the block one chosen tile sits in, not every tile of that shade in the yard.

The problem

The surround is a rectangular grid of glazed tiles, each with a shade code; two tiles sharing a code are the same glaze.

The tiler puts a thumb on the tile at row row, column col and reads its shade. Every tile reached from there through edge-sharing neighbours (up, down, left or right) of that same shade is recoated in shade shade. Corner to corner is not a step: grout runs between. A tile of that shade with no such path to the thumb keeps its old glaze.

Input. tiles — a list of lists of integers, the shade codes, rows all one length. row, col — the seed tile. shade — the new code.

Output. The grid after recoating.

Example.

tiles = [[7, 7, 4, 4],
         [7, 7, 4, 9],
         [3, 7, 9, 9],
         [3, 3, 9, 9]],  row = 0, col = 3, shade = 1

     -> [[7, 7, 1, 1],
         [7, 7, 1, 9],
         [3, 7, 9, 9],
         [3, 3, 9, 9]]

The seed is a 4, and three tiles of shade 4 are joined edge to edge, so three change. The 9s below are another shade and untouched.

A second example, where the new shade is the shade already there:

tiles = [[6, 6, 8],
         [6, 8, 8]],     row = 1, col = 0, shade = 6

     -> [[6, 6, 8],
         [6, 8, 8]]

Nothing changes. A careless fill repaints a 6 as a 6, sees a neighbour that still matches, and circles for ever.

Constraints.

• 1 <= len(tiles) <= 300, 1 <= len(tiles[0]) <= 300
• 0 <= tiles[r][c] <= 10^4 and 0 <= shade <= 10^4
• 0 <= row < len(tiles) and 0 <= col < len(tiles[0])

Hints

Approach

Brute force

Sweep the grid over and over, recoating any tile of the starting shade that touches a recoated one, until a pass changes nothing. A snake-shaped block needs one pass per tile: O((r · c)²), some 8 × 10⁹ reads on a 300 × 300 grid.

The insight

The tiles to recoat are the connected component of the seed under "same starting shade", so one traversal that paints as it pushes visits each exactly once.

Painting is the visited mark, so no separate seen grid is needed: a repainted tile no longer matches the starting shade and is never pushed twice. That holds only while the new shade differs from the old — when they are equal the mark is invisible, the traversal never ends, and the answer is the grid untouched.

Algorithm

1. Read target = tiles[row][col]; if target == shade, return the grid as is.
2. Paint the seed and push it on a stack.
3. Pop a tile; paint and push each of its four neighbours inside the grid that carries target.
4. Stop when the stack empties.

Complexity

Time O(r · c) — every tile is painted at most once and inspected from four neighbours. Space O(r · c) for the stack, which on a one-shade grid holds every tile.

Solution

"""Repainting the lido mosaic — flood fill the seed's block, painting as a mark."""


def solve(tiles, row, col, shade):
    rows, cols = len(tiles), len(tiles[0])
    target = tiles[row][col]          # read before painting: the grid forgets it
    grid = [list(line) for line in tiles]
    if target == shade:
        # Painting would be invisible, so the traversal could never terminate.
        return grid

    grid[row][col] = shade
    stack = [(row, col)]
    while stack:
        r, c = stack.pop()
        for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
            # Bounds checked explicitly: nr == -1 would wrap to the last row.
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == target:
                grid[nr][nc] = shade  # the paint is also the visited mark
                stack.append((nr, nc))
    return grid

TESTS = [
    (([[7, 7, 4, 4], [7, 7, 4, 9], [3, 7, 9, 9], [3, 3, 9, 9]], 0, 3, 1),
     [[7, 7, 1, 1], [7, 7, 1, 9], [3, 7, 9, 9], [3, 3, 9, 9]]),
    (([[6, 6, 8], [6, 8, 8]], 1, 0, 6),
     [[6, 6, 8], [6, 8, 8]]),                     # new shade equals the old one
    (([[2, 2], [5, 5], [2, 2]], 0, 0, 1),
     [[1, 1], [5, 5], [2, 2]]),                   # row -1 must not wrap round
    (([[4]], 0, 0, 9), [[9]]),
    (([[3, 3, 3], [3, 3, 3]], 1, 2, 0),
     [[0, 0, 0], [0, 0, 0]]),                     # one uniform block
    (([[5, 2, 5], [2, 5, 2], [5, 2, 5]], 1, 1, 8),
     [[5, 2, 5], [2, 8, 2], [5, 2, 5]]),          # corner joins do not count
]

Pitfalls

• Skipping the equal-shade check. The second example never returns: the stack keeps refilling with tiles that still match.
• Re-reading the seed's shade inside the loop. Once the seed is painted tiles[row][col] holds the new shade, so the fill matches the wrong glaze and stops after one tile.
• Trusting Python's negative indexing. tiles[-1][c] is the bottom row, not a miss, so a fill stepping up from row 0 lands on the far edge: [[2, 2], [5, 5], [2, 2]] seeded at row 0 recoats the bottom row too.

Variants

• Sheep that cannot stray — the same fill, seeded from the whole border.
• BFS and DFS — why a queue works here as well as a stack.