Surrounded Regions
Problem
The board contains "X" and "O". Capture every region of "O"s that is completely surrounded by "X" by flipping it to "X". A region touching the border is never captured. Modify the board in place.
Example 1
Input: [["X","X","X","X"], ["X","O","O","X"], ["X","X","O","X"], ["X","O","X","X"]] Output: [["X","X","X","X"], ["X","X","X","X"], ["X","X","X","X"], ["X","O","X","X"]]
The bottom O touches the border, so it survives.
Test cases
Case 1
Input: [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]] Expected: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Case 2
Input: [["X"]] Expected: [["X"]]
Case 3
Input: [["O","O"],["O","O"]] Expected: [["O","O"],["O","O"]]
View solutionHide solution1 approach
1. Protect border-connected cells, flip the rest
Time O(R·C)Space O(R·C) recursion worst case
Any "O" connected to the border survives. Mark those from the border as "S", flip remaining "O" to "X", then restore "S" to "O".
function solve(board) { const R = board.length, C = board[0].length; const mark = (r, c) => { if (r < 0 || c < 0 || r >= R || c >= C || board[r][c] !== 'O') return; board[r][c] = 'S'; mark(r + 1, c); mark(r - 1, c); mark(r, c + 1); mark(r, c - 1); }; for (let r = 0; r < R; r++) { mark(r, 0); mark(r, C - 1); } for (let c = 0; c < C; c++) { mark(0, c); mark(R - 1, c); } for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) board[r][c] = board[r][c] === 'S' ? 'O' : 'X';}