• m == board.length, n == board[i].length
• 1 <= m, n <= 200
• board[i][j] is the character 'X' or 'O'
• Cells touching only at a corner are not connected.
• Every 'O' on the outer edge is safe by definition, whatever surrounds it.

The condition to test is negative — a region is captured when it cannot reach the border — and negative conditions are awkward to check directly. You cannot confirm that no escape route exists without examining every possible route. That awkwardness is the whole difficulty, and the fix is to stop testing the negative.

Take each 'O' and search for a way out to the edge. If the search finds one, leave the cell; otherwise flip it.

for r, c in all_cells:
    if board[r][c] == 'O':
        if not can_reach_border(r, c):     # a full search, from every cell
            board[r][c] = 'X'

Two problems. First the cost: each search can sweep the board, so with up to m × n cells each costing up to m × n, the total is O((m × n)²) — at 200 × 200 that is 1.6 billion steps.

Second, and more damaging, is a correctness trap. Flipping cells as you scan changes the board while later searches are still using it. A cell captured early can wall off a route that a later cell depended on, and results become order-dependent. You would have to collect every decision first and apply them all afterwards.

But the deeper waste is this: every cell in a region runs its own escape search over the same territory, all asking a question that has a single answer for the whole region. Whether a region escapes is a property of the region. It should be decided once.

Flip the question. Rather than asking which regions are trapped, ask which are safe — and safety, unlike being trapped, has an easy positive definition that spreads.

A cell is safe if it is an 'O' on the border, or if it is an 'O' adjacent to a safe cell. That is a rule that propagates outward from a known starting set, which is exactly what a traversal does well. Nothing has to be proved absent.

So: seed a traversal from every 'O' on the four edges at once, spread through connected 'O's, and mark everything reached. Then sweep the board. Any 'O' still unmarked was never reachable from any border cell, which is precisely the definition of surrounded — so flip it. Restore the marked ones.

Everything is decided by one traversal instead of thousands, and the awkward negative test becomes a simple check for the absence of a mark.

Seeding all border cells together rather than running a separate traversal per border cell is worth naming: it is a multi-source traversal, and it is not many searches but one search whose starting set has many members. Since we only care whether a cell was reached and not from which seed, the extra sources cost nothing.

The board has two symbols but the algorithm needs three meanings: wall, safe 'O', and not-yet-known 'O'. The standard trick is a temporary third character.

Traverse from the border marking safe cells as 'T'. After the traversal every cell means exactly one thing: 'X' is a wall, 'T' is a safe 'O', and any remaining 'O' is surrounded. Then a single sweep converts 'O' to 'X' and 'T' back to 'O'.

def solve(board):
    if not board or not board[0]:
        return
    rows, cols = len(board), len(board[0])

    def mark_safe(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != 'O':
            return                        # base case: off-board, a wall, or already marked
        board[r][c] = 'T'                 # mark BEFORE recursing
        mark_safe(r + 1, c)
        mark_safe(r - 1, c)
        mark_safe(r, c + 1)
        mark_safe(r, c - 1)

    for r in range(rows):                 # seed every border cell
        mark_safe(r, 0)
        mark_safe(r, cols - 1)
    for c in range(cols):
        mark_safe(0, c)
        mark_safe(rows - 1, c)

    for r in range(rows):                 # single sweep decides everything
        for c in range(cols):
            if board[r][c] == 'O':
                board[r][c] = 'X'         # never reached: surrounded
            elif board[r][c] == 'T':
                board[r][c] = 'O'         # reached: restore

The traversal enters each cell at most once and the sweep visits each cell once, so the whole thing is O(m × n) time with no extra memory beyond the recursion stack.

X X X X
X O O X
X X O X
X O X X

Seeding the border. Walking the edges: the entire top row is 'X', the entire left column is 'X', the right column is 'X', and the bottom row is X, O, X, X. The only border 'O' is at (3,1).

The traversal. mark_safe(3,1) fires. The cell is an 'O', so it becomes 'T'. Its neighbours: below is off the board; above is (2,1), which holds 'X'; left is (3,0), an 'X'; right is (3,2), an 'X'. All four return immediately and the traversal ends having marked exactly one cell.

Every other mark_safe call from the border seeds hits an 'X' and returns at once. The interior region at (1,1), (1,2) and (2,2) is never touched — nothing on the border connects to it.

The sweep. Now each cell is decided.

Final board: all 'X' except (3,1). That interior region really was sealed — its cells are bounded by 'X' at (0,1), (0,2), (1,0), (1,3), (2,1), (2,3) and (3,2), with no gap.

Now the second example, the vertical pair:

X O X
X O X
X X X

Border seeding reaches (0,1) on the top edge. It becomes 'T', and recursing downward reaches (1,1), which is an 'O' and becomes 'T' too. The sweep finds no plain 'O' anywhere, restores both 'T's, and the board is unchanged. The cell (1,1) is fully interior and would have been captured on its own — it survives only because safety propagated to it through its neighbour. That is why the region, not the cell, is the unit of judgement.

The idea to extract is inverting a hard-to-verify condition into an easy-to-propagate one. Proving a cell has no escape route requires exhausting all routes. Proving a cell is reachable from the border requires only reaching it. Same information, and one direction is dramatically cheaper.

Look for the signature: a problem asking which items lack a property that spreads through connections. Compute the complement — the items that have it — with one multi-source traversal from the known sources, then take everything left over. This is exactly the move behind Pacific Atlantic Water Flow, where instead of asking which cells drain to an ocean, you sit on the ocean and climb inland. Same shape, different rule.

Two supporting techniques recur alongside it. Border seeding: whenever the edge of a grid has special status — safe, exposed, an exit — every edge cell becomes a source. And the temporary third symbol: when you need to distinguish three states on a two-symbol board, borrow an unused character rather than allocating a parallel grid, then normalise in a final sweep.

Depth-first search is the natural fit because the question is pure reachability with no distances involved; breadth-first search visits precisely the same cells for the same answer. On a 200 × 200 board a snaking region can nest 40,000 recursive calls, though, so an explicit stack or a queue is the safer implementation at that size.

Train the reflex: when asked to find everything not connected to something, do not go looking for absence. Traverse from the thing, mark what you reach, and take the remainder.