Surrounded Regions

Capture all 'O' regions not connected to border. Replace captured 'O' with 'X'.

Example 1

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"]]

Example 2

Input: board=[["X"]] → Output: [["X"]]

Solution Approach

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

Java

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)