Capture Regions On Board
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.graphs;
import java.util.*;
/
* ============================================================================================
* PROBLEM: Capture Regions on Board
* ============================================================================================
*
* ---------------------
* 1. Problem Description
* ---------------------
* Given an N x M board containing 'X' and 'O'. A region of 'O's is "captured" (flipped to 'X')
* if it is completely surrounded by 'X's.
* * Boundary Rule:
* Any 'O' on the boundary, or connected to an 'O' on the boundary, cannot be captured.
*
* ---------------------
* 2. Logical Breakdown & Mathematical Formulation
* ---------------------
* Instead of finding surrounded regions directly, it is mathematically simpler to find
* "unsurroundable" regions using a Flood Fill approach starting from the boundaries.
*
* Step 1: Boundary DFS/BFS
* - Traverse the four boundaries of the matrix:
* - Top row, Bottom row, Left column, Right column.
* - For every 'O' found on the boundary, initiate a DFS/BFS to find all connected 'O's.
* - Mark these "safe" 'O's with a temporary placeholder (e.g., '').
*
* Step 2: Final Transformation
* - Iterate through the entire matrix:
* - If an element is 'O', it must be surrounded (since it wasn't reached from the boundary).
* Flip it to 'X'.
* - If an element is our placeholder '', it is safe. Flip it back to 'O'.
* - If an element is 'X', leave it as is.
*
* ---------------------
* 3. Constraints & Complexity Analysis
* ---------------------
* Constraints:
* 1 <= N, M <= 1000
*
* Time Complexity:
* O(N * M) - Every cell is visited at most twice (once for boundary check/DFS, once for final flip).
*
* Space Complexity:
* O(N * M) - In the worst case, the recursion stack (DFS) or queue (BFS) can grow to the size
* of the board.
* ============================================================================================
*/
public class CaptureRegionsOnBoard {
public int solve(ArrayList