118. Surrounded Regions

An 'O' survives only if it can reach the border. So instead of hunting for surrounded regions, flood-fill from every border 'O' to mark all connected 'O's as safe; then flip everything else ('O' → 'X') and restore the safe ones.

Idea

An 'O' region is captured unless it touches the edge. Rather than test each region for being surrounded, invert the problem: the only regions that survive are those connected to a border 'O'.

So we flood-fill inward from every 'O' on the border, temporarily marking reachable cells '#' (safe). After that, any remaining 'O' must be fully enclosed → flip it to 'X'; and every '#' is restored to 'O'.

Algorithm

1. Push every border cell that is 'O' onto a BFS queue and mark it '#'.
2. BFS: for each dequeued cell, visit 4-neighbors; mark any neighboring 'O' as '#' and enqueue it.
3. Sweep the whole board: 'O' → 'X' (captured), '#' → 'O' (restored).

Worked example

For [[X,X,X,X],[X,O,O,X],[X,X,O,X],[X,O,X,X]]:

• The only border 'O' is at (3,1). Flood from it — it has no 'O' neighbors, so only (3,1) is safe.
• The middle region (1,1),(1,2),(2,2) touches no border → captured to 'X'.
• Restore (3,1) back to 'O'.

Result: [[X,X,X,X],[X,X,X,X],[X,X,X,X],[X,O,X,X]].

Complexity

• Time: O(m·n) — each cell visited a constant number of times.
• Space: O(m·n) worst case for the BFS queue.

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public char[][] solve(char[][] board) {
        if (board.length == 0 || board[0].length == 0) {
            return board;
        }
        int m = board.length, n = board[0].length;
        Deque<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && board[i][j] == 'O') {
                    board[i][j] = '#';
                    q.offer(new int[]{i, j});
                }
            }
        }
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!q.isEmpty()) {
            int[] cell = q.poll();
            for (int[] d : dirs) {
                int ni = cell[0] + d[0], nj = cell[1] + d[1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && board[ni][nj] == 'O') {
                    board[ni][nj] = '#';
                    q.offer(new int[]{ni, nj});
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                else if (board[i][j] == '#') board[i][j] = 'O';
            }
        }
        return board;
    }
}