Sheep that cannot stray

A hill farm maps its moor square by square. Bog stops a sheep, the edge of the map does not, and a sheep that walks off the edge is the next farm's problem.

The problem

The survey divides the moor into a rectangular grid of squares. A square holds G where the ground is grass a sheep will walk on, and B where it is bog the flock refuses to cross.

A sheep steps between grass squares that share an edge — up, down, left or right; squares meeting only at a corner are not joined, because the bog between them is unbroken. From a grass square on the outer edge of the map a sheep takes one step off the survey and is gone.

Count the grass squares from which no sequence of steps ever reaches the edge of the map. The count is of squares, not patches: a sealed-in patch of nine squares contributes nine.

Input. moor — a list of strings of equal length, each character G or B.

Output. An integer: how many grass squares are sealed in.

Example.

moor = ["BBBB",
        "GBGB",
        "BGGB",
        "BBBB"]   ->  3

The lone G in the left column sits on the map edge, so a sheep there walks off. The other three form one patch ringed by bog, touching no edge: three sealed squares.

A second example, with two sealed patches of different sizes:

moor = ["BBBBB",
        "BGGBB",
        "BBGBB",
        "GBBGB",
        "BBBBB"]   ->  4

Three squares in the upper patch and one on its own in row 3 are sealed; the G in the left column escapes. Counting patches would answer 2.

Constraints.

• 1 <= len(moor) <= 500
• 1 <= len(moor[0]) <= 500, every row the same length
• every character is G or B

Hints

Approach

Brute force

Start a search at each grass square and see whether it reaches the edge. One search visits up to r · c squares, from up to r · c starting squares, so a 500 × 500 moor costs about 6 × 10¹⁰ steps.

The insight

Ask which squares the border can reach, instead of asking square by square which squares can reach the border.

Movement here is symmetric — every step has a reverse step — so a sheep escapes from a square exactly when that square is connected to a grass square on the border. One flood seeded with every border grass square at once marks all of them, and whatever it misses is sealed. The precondition is that symmetry: on a one-way graph the trick needs the reversed edges built first.

Algorithm

1. Build a seen grid of the same shape, all false.
2. Push every grass square on the outer ring, marking each as it is pushed.
3. Pop a square; for each of its four neighbours that is grass and unmarked, mark it and push it.
4. When the stack empties, count the grass squares still unmarked.

Complexity

Time O(r · c) — each square is pushed at most once, pops once, and looks at four neighbours. Space O(r · c) for seen, plus a stack that on an all-grass moor holds every square.

Solution

"""Sheep that cannot stray — flood inward from the border, count the grass left."""


def border_squares(rows, cols):
    """Every square on the outer ring, each listed once."""
    ring = {(r, c) for r in range(rows) for c in (0, cols - 1)}
    ring |= {(r, c) for c in range(cols) for r in (0, rows - 1)}
    return ring


def solve(moor):
    rows, cols = len(moor), len(moor[0])
    escapes = [[False] * cols for _ in range(rows)]

    stack = []
    for r, c in border_squares(rows, cols):
        if moor[r][c] == "G" and not escapes[r][c]:
            escapes[r][c] = True       # mark on push: every square enters once
            stack.append((r, c))

    while stack:
        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 moor[nr][nc] == "G" and not escapes[nr][nc]:
                escapes[nr][nc] = True
                stack.append((nr, nc))

    # Movement is symmetric, so an unmarked grass square cannot reach the border.
    return sum(1 for r in range(rows) for c in range(cols)
               if moor[r][c] == "G" and not escapes[r][c])

TESTS = [
    ((["BBBB", "GBGB", "BGGB", "BBBB"],), 3),
    ((["BBBBB", "BGGBB", "BBGBB", "GBBGB", "BBBBB"],), 4),
    ((["GGGG"],), 0),                        # one row: every square is on the edge
    ((["BBB", "BGB", "BBB"],), 1),           # a single sealed square
    ((["GGG", "GGG", "GGG"],), 0),           # all grass, all of it connected out
    ((["BBBBB", "BGGGB", "BGBGB", "BGGGB", "BBBBB"],), 8),  # ring round a bog core
    ((["B"],), 0),
]

Pitfalls

• Counting patches instead of squares. The second example answers 2 rather than 4; each sealed patch is worth its own size.
• Recursing. A recursive fill runs 250,000 frames deep on an all-grass 500 × 500 moor and dies with a recursion error. Keep an explicit stack.
• Eight-way steps. In the first example the border square in row 1 touches the sealed patch corner to corner, so a diagonal flood frees all three squares and answers 0.

Variants

• Blue mould on the bench — the same wave over a grid, but carrying a distance with it.
• Union-find — the same components built by merging squares rather than flooding them.