Surrounded Regions
In a board of X and O, capture every region of Os that is completely surrounded by Xs by flipping those Os to X. A region touching the border is never captured.
Intuition
The direct approach — flood each O region and ask whether it is enclosed — forces you to carry an 'escaped to the border' flag out of the recursion and then revisit the region to flip it. Invert the question. A region survives exactly when it touches the border, so flood inward from the border and mark everything reachable as safe. Every O left unmarked is enclosed by definition, and can be flipped in a final sweep. No flags, and each cell is visited a constant number of times.
Invert the condition. Finding regions that don't touch the border is hard; finding the ones that do is a flood fill from the edges. Mark those as safe, then everything still unmarked is by definition surrounded. Solving the complement is often far easier than the stated problem.
Approach
See why the direct version is awkward
Starting a DFS at an interior O, you must determine whether any cell in that region touches the edge. That means either threading a boolean back up through every recursive call, or collecting the region into a list and checking it afterwards. Both work, but both mix the traversal with the decision, and the flag version is easy to get subtly wrong when a region has several branches.
Flood inward from the border instead
Collect every O sitting on the outer ring — top row, bottom row, first column, last column. Each is unambiguously safe, and so is every O connected to it. Run a DFS or BFS from each of these seeds, marking cells safe as you go. This traversal never has to decide anything: reachability from the border is the answer.
Sweep once and flip what was never marked
After the flood, walk the whole board. Any O that was not marked safe could not reach the border, so it is enclosed — flip it to X. Marked cells stay O. In an in-place implementation the marking is often done by writing a temporary character such as #, then converting # back to O and every remaining O to X in the final sweep. Two passes, O(mn) total.
Solution & live demo
Common pitfalls
Flood filling from interior cells and checking for escape
for each interior 'O': dfs and test if it reaches the border
seed the stack with border 'O' cells only
That re-explores the same region once per starting cell and needs bookkeeping to remember which regions already escaped. Starting from the border touches each safe cell exactly once.
Missing corner cells in the border scan
for c in range(C):
if board[0][c] == 'O': ...if (r in (0, R - 1) or c in (0, C - 1)) and board[r][c] == 'O':
Scanning only the top and bottom rows omits the left and right columns (and vice versa), leaving whole safe regions unmarked. The combined row-or-column test covers all four sides including corners.
Flipping cells during the flood instead of after
board[nr][nc] = 'O' # already 'O'
board[nr][nc] = '#' # ... final pass restores '#' -> 'O', 'O' -> 'X'
The flood needs a third symbol to distinguish "safe, already visited" from "unvisited". Without it there's no way to tell a protected region from an unexamined one, and the final rewrite can't be done.
Edge cases
Everything is marked safe and the board is unchanged.
Every cell is on the border, so nothing can ever be captured.
There are no seeds and no flips; the board is returned as-is.
The flood follows the corridor inward and marks the entire region safe — which is why flooding from the border is more robust than trying to judge enclosure locally.