Surrounded Regions

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

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"]]
Explanation: Notice that an 'O' should not be flipped if:
- It is on the border, or
- It is adjacent to an 'O' that should not be flipped.
The bottom 'O' is on the border, so it is not flipped.
The other three 'O' form a surrounded region, so they are flipped.

Example 2:

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

Constraints:

• m == board.length

• n == board[i].length

• 1 <= m, n <= 200

• board[i][j] is 'X' or 'O'.

Solutions

Depth-First Search (DFS) Solution: The DFS solution works by treating the board as a graph, where each cell is a node and each node is connected to its neighbors. The algorithm starts by marking all 'O’s on the border of the board as 'B’s, indicating that they are not surrounded by 'X’s and should not be flipped. It does this by performing a DFS starting from each ‘O’ on the border, and for each ‘O’ it encounters during the DFS, it marks it as ‘B’ and continues the DFS on its neighbors.

After all 'O’s connected to the border have been marked as 'B’s, the algorithm then traverses the entire board and flips all remaining 'O’s to 'X’s, because these 'O’s are not connected to the border and are therefore surrounded by 'X’s. It also flips all 'B’s back to 'O’s, because these 'O’s are not surrounded by 'X’s and should not be flipped.

Breadth-First Search (BFS) Solution: The BFS solution works in a similar way, but instead of using DFS to mark the 'O’s that should not be flipped, it uses BFS. The algorithm starts by adding all 'O’s on the border to a queue. Then, while there are still nodes in the queue, it dequeues a node, marks it as ‘B’, and enqueues all of its neighbors that are 'O’s. This process continues until the queue is empty, at which point all 'O’s connected to the border have been marked as 'B’s.

After that, the algorithm traverses the entire board and flips all remaining 'O’s to 'X’s, and flips all 'B’s back to 'O’s, just like in the DFS solution.

Both of these solutions effectively solve the problem by identifying all 'O’s that are not surrounded by 'X’s and marking them so they are not flipped in the final step. The main difference between them is the order in which they visit the nodes (DFS goes deep into the graph first, while BFS visits all neighbors first), but they both produce the correct result.

public class Solution {
    public void Solve(char[][] board) {
        if (board == null || board.Length == 0) return;
        int m = board.Length, n = board[0].Length;
        Queue<int[]> queue = new Queue<int[]>();

        // Enqueue all 'O's on the border
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if ((i == 0 || j == 0 || i == m - 1 || j == n - 1) && board[i][j] == 'O')
                    queue.Enqueue(new int[] { i, j });

        // BFS from the border 'O's
        while (queue.Count > 0) {
            int[] cell = queue.Dequeue();
            int row = cell[0], col = cell[1];
            if (row < 0 || col < 0 || row >= m || col >= n || board[row][col] != 'O') continue;
            board[row][col] = 'B';
            queue.Enqueue(new int[] { row - 1, col });
            queue.Enqueue(new int[] { row + 1, col });
            queue.Enqueue(new int[] { row, col - 1 });
            queue.Enqueue(new int[] { row, col + 1 });
        }

        // Flip all 'O's to 'X's and 'B's back to 'O's
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                board[i][j] = board[i][j] == 'B' ? 'O' : 'X';
    }
}

The time complexity is still O(m*n) and the space complexity is O(min(m, n)) because in the worst case the queue will store all the cells in the border, which is min(m, n).