Surrounded Regions
Capture regions that are fully surrounded by 'X'.
Examples
The 'O' at the bottom is connected to the border, so it's not surrounded. The center island is surrounded and flipped.
Problem Understanding
Given an m x n board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
Key Insight: An 'O' is NOT surrounded if connects to an 'O' on the boundary.
Algorithm Strategy (Reverse Thinking)
Instead of searching for surrounded regions (hard), let's search for Unsurrounded regions (easy).
- Border Check: Any 'O' on the border is safe. Any 'O' connected to a border 'O' is also safe.
- Phase 1 (Mark Safe): Call DFS on every cell of the 4 borders. DFS returns at once unless the cell is an 'O', and marks every 'O' it reaches as 'T' (temporarily safe).
- Phase 2 (Flip): Iterate over the entire grid.
- If cell is 'O' (Unmarked) -> It's trapped. Flip to 'X'.
- If cell is 'T' (Marked) -> It's safe. Flip back to 'O'.
Visualization
Two passes. First, DFS runs from every border cell — each row's left and right cell, then each column's top and bottom cell — and marks every 'O' it reaches as 'T'. Corner cells are called twice, once from their row and once from their column; when a corner is an 'O', the second call finds it already 'T' and returns. Then one pass over the whole board captures every 'O' still unmarked (red) and restores every 'T' to 'O' (green).
Dry Run
Board:
X O X
X O X
X X X
| Step | Pass | Call or cell | Action |
|---|---|---|---|
| 1 | Border rows | dfs(0,0), dfs(0,2), dfs(1,0), dfs(1,2), dfs(2,0), dfs(2,2) |
Each cell is 'X' — every call returns. |
| 2 | Border columns | dfs(0,0), dfs(2,0) |
'X' — return. |
| 3 | Border columns | dfs(0,1) |
'O' — mark 'T'. Call down. |
| 4 | inside dfs(0,1) |
dfs(1,1) |
'O' — mark 'T'. Down (2,1) is 'X', up (0,1) is 'T', right (1,2) and left (1,0) are 'X' — all return. |
| 5 | back in dfs(0,1) |
up, right, left | (-1,1) is outside, (0,2) and (0,0) are 'X' — return. |
| 6 | Border columns | dfs(2,1), dfs(0,2), dfs(2,2) |
'X' — return. |
| 7 | Flip | (0,1), (1,1) |
'T' — restore to 'O'. |
| 8 | Flip | every other cell | 'X' — keep. |
No 'O' was left unmarked, so nothing is captured: the column of 'O's escapes through the top edge.
Edge Cases & Common Mistakes
- No 'O' on Border: If all border cells are 'X', ANY 'O' inside is trapped. They will all be flipped.
- All 'O' Board: If grid is full of 'O's, they are all connected to border. None flipped.
- Small Grid: 1x1 or 2x2 grid cannot have any captured region (all cells touch border).
Solution
Using the Border DFS technique.
Surrounded Regions Code
1var solve = function(board) {2 const rows = board.length, cols = board[0].length;34 function dfs(r, c) {5 if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== 'O') {6 return;7 }8 board[r][c] = 'T';9 dfs(r + 1, c);10 dfs(r - 1, c);11 dfs(r, c + 1);12 dfs(r, c - 1);13 }1415 for (let r = 0; r < rows; r++) {16 dfs(r, 0);17 dfs(r, cols - 1);18 }19 for (let c = 0; c < cols; c++) {20 dfs(0, c);21 dfs(rows - 1, c);22 }2324 for (let r = 0; r < rows; r++) {25 for (let c = 0; c < cols; c++) {26 if (board[r][c] === 'O') {27 board[r][c] = 'X';28 } else if (board[r][c] === 'T') {29 board[r][c] = 'O';30 }31 }32 }33};