Problem Overview

You are given an m x n matrix board containing characters 'X' and 'O'.
You need to capture all regions surrounded by 'X'.

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

A region is considered surrounded if it is completely enclosed by 'X's from all sides — top, bottom, left, and right.
However, any 'O' connected to the border (directly or indirectly) cannot be captured.

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:
The 'O' at the bottom left corner is not surrounded, because it is connected to the boundary.

---

Intuition / Approach

1. Key Observation

Only 'O's that are connected to the borders can escape being surrounded.
Therefore:

• If an 'O' is on the boundary (top, bottom, left, or right) or connected to one, it should not be flipped.
• All other 'O's must be flipped to 'X'.

2. Main Idea

We can:

1. Traverse all border cells.
2. Whenever we find 'O' on the border, perform DFS or BFS from there and mark all connected 'O's as safe (temporarily change 'O' → 'T').
3. Finally, iterate through the entire board:
   • Convert all remaining 'O' → 'X' (they are captured).
   • Convert all 'T' → 'O' (they are safe and connected to borders).

---

Algorithm Explanation (DFS Version)

1. Mark Border-connected O’s:
   • Loop through first and last rows, and first and last columns.
   • For each 'O' on the border, call DFS to mark it and its connected 'O's as 'T'.
2. DFS Function:
   • Base Case: If the cell is out of bounds or not 'O', return.
   • Otherwise, mark it as 'T'.
   • Recurse for 4 directions (up, down, left, right).
3. Final Transformation:
   • Traverse the board:
     • 'O' → 'X' (captured)
     • 'T' → 'O' (safe)

This ensures only the enclosed regions are flipped.

---

Step-by-Step Example

Consider:

[
  ['X','X','X','X'],
  ['X','O','O','X'],
  ['X','X','O','X'],
  ['X','O','X','X']
]

• Border 'O' found at (3,1) → mark it 'T'
• DFS from (3,1) doesn’t reach any other 'O's.
• Remaining 'O's (not connected to the border) → flipped to 'X'.

Final state:

[
  ['X','X','X','X'],
  ['X','X','X','X'],
  ['X','X','X','X'],
  ['X','O','X','X']
]

---

Java Code Implementation

public class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        
        int rows = board.length;
        int cols = board[0].length;
        
        // Step 1: Mark all border-connected 'O's as 'T'
        for (int i = 0; i < rows; i++) {
            dfs(board, i, 0);
            dfs(board, i, cols - 1);
        }
        for (int j = 0; j < cols; j++) {
            dfs(board, 0, j);
            dfs(board, rows - 1, j);
        }
        
        // Step 2: Flip all remaining 'O' to 'X', and 'T' back to 'O'
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X'; // captured region
                } else if (board[i][j] == 'T') {
                    board[i][j] = 'O'; // safe region
                }
            }
        }
    }
    
    private void dfs(char[][] board, int i, int j) {
        int rows = board.length;
        int cols = board[0].length;
        
        // Boundary check
        if (i < 0 || j < 0 || i >= rows || j >= cols || board[i][j] != 'O') {
            return;
        }
        
        // Mark current cell as safe
        board[i][j] = 'T';
        
        // Explore neighbors (up, down, left, right)
        dfs(board, i + 1, j);
        dfs(board, i - 1, j);
        dfs(board, i, j + 1);
        dfs(board, i, j - 1);
    }
}

---

Alternative Approach – BFS

Instead of DFS recursion, you can use a queue (BFS) to iteratively mark border-connected 'O's.
The logic is identical; only traversal method differs.

---

Time and Space Complexity

Complexity	Description
Time Complexity	O(M × N) — Every cell is visited at most once.
Space Complexity	O(M × N) — DFS recursion or BFS queue may use space proportional to grid size.

---

Key Takeaways

• Always look for border-connected components in such grid problems.
• Use temporary marking ('T') to avoid confusion during traversal.
• After marking safe regions, it’s easy to finalize the transformation in one pass.