Capture all 'O' regions not connected to border. Replace captured 'O' with 'X'.
Input: board=[["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"]]
Input: board=[["X"]] → Output: [["X"]]
DFS from all border 'O' cells marking them safe. Then flip remaining 'O' to 'X' and restore safe ones.
- DFS from all border O cells: mark them 'S' (safe)
- Iterate entire board: O becomes X, S becomes O
public void solve(char[][] board) {
int m = board.length, n = board[0].length;
for (int i = 0; i < m; i++) { dfs(board,i,0); dfs(board,i,n-1); }
for (int j = 0; j < n; j++) { dfs(board,0,j); dfs(board,m-1,j); }
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++)
board[i][j] = board[i][j] == 'S' ? 'O' : 'X';
}
private void dfs(char[][] b, int i, int j) {
if (i<0||i>=b.length||j<0||j>=b[0].length||b[i][j]!='O') return;
b[i][j]='S';
dfs(b,i+1,j); dfs(b,i-1,j); dfs(b,i,j+1); dfs(b,i,j-1);
}
- Time Complexity: O(m*n)
- Space Complexity: O(m*n)