130. Surrounded Regions
You are given an m × n board where every cell is either X or O. A region is a group of O cells connected up/down/left/right. A region is captured — every one of its cells flips to X — unless at least one of its cells lies on the border of the board. Border-touching regions are safe and stay as they are.
Your function receives the board as a list of m row strings and returns the board after all captures, in the same row-string form.
Diagonal contact does not connect cells, and safety spreads through a whole region: if any cell of a region can reach the border, every cell of that region survives.
Example 1:
Input: board = ["XXXX", "XOOX", "XXOX", "XOXX"]
Output: ["XXXX", "XXXX", "XXXX", "XOXX"]
Explanation: The three connected O's in the middle never touch the border, so they are captured. The O at row 3, column 1 sits on the bottom border and survives.
Example 2:
Input: board = ["OXO", "XOX", "OXO"]
Output: ["OXO", "XXX", "OXO"]
Explanation: The center O is walled in on all four sides, so it flips. The four corner O's are on the border and are safe (diagonals do not connect them to anything).
Constraints:
- 1 ≤ m, n ≤ 200
- Every cell is either 'X' or 'O'
- Cells connect only horizontally and vertically, never diagonally
Hints:
Deciding each region's fate directly means flood-filling it while checking whether any of its cells lies on the border — doable, but there is a cleaner direction to think in.
Flip the question: a cell survives exactly when it can reach the border through O's. Which O cells are trivially safe, before any search?
Flood fill (BFS/DFS) starting from every border O marks all safe cells in one sweep. Everything still unmarked and 'O' gets captured. A grid this size can make deep recursion risky — an explicit stack or queue is the sturdy choice.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: board = ["XXXX", "XOOX", "XXOX", "XOXX"]
Expected output: ["XXXX", "XXXX", "XXXX", "XOXX"]