Pattern visualizer

Surrounded Regions

Searching for enclosed regions directly is awkward: you cannot tell a region is surrounded until you have seen all of it, so a half-finished walk proves nothing. Inverting the question removes that problem entirely. A region survives exactly when it touches an edge, and that is checkable from the outside in — start a search at every border O, mark everything it reaches, and stop. One pass over the border decides every cell on the board: whatever the search never touched is enclosed, by definition rather than by re-checking. The third marker value (#) exists only to keep 'survived' distinct from 'was always X' until the final sweep. Animated on: board = [[X,X,X,X,X],[X,O,O,X,O],[X,X,O,X,O],[X,O,X,X,O]] — flip every O region that is fully enclosed by X..

Search inward from the border, then capture what is left

time O(rows * cols)space O(rows * cols) recursion stackstep 1 / 13

board

01234

0123

line 1

A region of O's is captured only if NONE of its cells touches an edge. So instead of hunting for enclosed regions, find the few that escape: every O reachable from the border survives, and everything else is surrounded by definition.

Pseudocode

1FUNCTION solve(board):
2  FOR each border cell (r, c):
3    IF board[r][c] = 'O': mark(r, c)
4  FOR each cell (r, c):
5    IF board[r][c] = 'O': board[r][c] <- 'X'
6    IF board[r][c] = '#': board[r][c] <- 'O'
7  RETURN board
8FUNCTION mark(r, c):
9  IF (r, c) outside board OR board[r][c] != 'O': RETURN
10  board[r][c] <- '#'
11  mark(r-1, c)
12  mark(r+1, c)
13  mark(r, c-1)
14  mark(r, c+1)

← / → step · space play · Home restart

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap