Surrounded regions

Flip every 'O' to 'X' unless it connects back to the border. Flood fill from the border first, so you never have to guess.

Time O(rows × cols)Space O(rows × cols)Code C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Flipping "surrounded" O's directly is awkward, because an O only counts as surrounded once you know none of its region touches the border. Flip the problem: flood fill from every border O first and mark that whole region safe. Anything still plain 'O' afterwards never reached the border, so it is surrounded and becomes 'X'.

Code

public static void Solve(char[][] board) {
    int rows = board.Length, cols = board[0].Length;
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            if ((r == 0 || c == 0 || r == rows - 1 || c == cols - 1) && board[r][c] == 'O')
                Mark(board, r, c);
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            if (board[r][c] == 'O') board[r][c] = 'X'; // never reached the border: surrounded
            else if (board[r][c] == '#') board[r][c] = 'O'; // reached the border: safe, restore it
}

static void Mark(char[][] board, int r, int c) {
    if (r < 0 || c < 0 || r >= board.Length || c >= board[0].Length || board[r][c] != 'O') return;
    board[r][c] = '#'; // safe: temporarily mark it
    Mark(board, r + 1, c); Mark(board, r - 1, c);
    Mark(board, r, c + 1); Mark(board, r, c - 1);
}

Tips

Only start the flood fill from border cells; starting from everywhere would mark every O safe.
Use a third marker (here '#') so "safe" and "still unknown" are never confused during the scan.

In the .NET library

This border-first flood fill is the standard trick whenever "reachable from the edge" matters: the same idea solves "number of enclaves" and parts of "pacific atlantic water flow".