Given an m x n matrix board containing 'X' and 'O', capture all regions that are completely surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
A region is surrounded if it's completely enclosed by 'X' cells with no path to the border of the board.
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' at position (3,1) is connected to the border and should not be captured, while the other regions are surrounded and captured.
Input:
board = [["X"]]
Output:
[["X"]]
The key insight is to work backwards: instead of finding surrounded regions, find regions that are NOT surrounded (connected to borders), then capture everything else.
Mark Border-Connected O's:
Capture Surrounded Regions:
Restore Safe Regions:
1class Solution {
2 private int m, n;
3 private int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
4
5 public void solve(char[][] board) {
6 if (board == null || board.length == 0 || board[0].length == 0) {
7 return;
8 }
9
10 m = board.length;
11 n = board[0].length;
12
13 // Step 1: Mark all O's connected to borders as safe (T)
14 // Check top and bottom borders
15 for (int j = 0; j < n; j++) {
16 if (board[0][j] == 'O') {
17 dfs(board, 0, j);
18 }
19 if (board[m - 1][j] == 'O') {
20 dfs(board, m - 1, j);
21 }
22 }
23
24 // Check left and right borders
25 for (int i = 0; i < m; i++) {
26 if (board[i][0] == 'O') {
27 dfs(board, i, 0);
28 }
29 if (board[i][n - 1] == 'O') {
30 dfs(board, i, n - 1);
31 }
32 }
33
34 // Step 2: Capture surrounded O's and restore safe O's
35 for (int i = 0; i < m; i++) {
36 for (int j = 0; j < n; j++) {
37 if (board[i][j] == 'O') {
38 board[i][j] = 'X'; // Capture surrounded
39 } else if (board[i][j] == 'T') {
40 board[i][j] = 'O'; // Restore safe
41 }
42 }
43 }
44 }
45
46 private void dfs(char[][] board, int row, int col) {
47 // Mark as safe (temporarily)
48 board[row][col] = 'T';
49
50 // Explore all 4 directions
51 for (int[] dir : directions) {
52 int newRow = row + dir[0];
53 int newCol = col + dir[1];
54
55 // Check bounds and if it's an unmarked O
56 if (newRow >= 0 && newRow < m &&
57 newCol >= 0 && newCol < n &&
58 board[newRow][newCol] == 'O') {
59 dfs(board, newRow, newCol);
60 }
61 }
62 }
63}
64
65/**
66 * Alternative solution using BFS instead of DFS
67 */
68class SolutionBFS {
69 public void solve(char[][] board) {
70 if (board == null || board.length == 0) return;
71
72 int m = board.length;
73 int n = board[0].length;
74 Queue<int[]> queue = new LinkedList<>();
75
76 // Add all border O's to queue
77 for (int j = 0; j < n; j++) {
78 if (board[0][j] == 'O') queue.offer(new int[]{0, j});
79 if (board[m - 1][j] == 'O') queue.offer(new int[]{m - 1, j});
80 }
81 for (int i = 0; i < m; i++) {
82 if (board[i][0] == 'O') queue.offer(new int[]{i, 0});
83 if (board[i][n - 1] == 'O') queue.offer(new int[]{i, n - 1});
84 }
85
86 // BFS to mark all border-connected O's
87 int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
88 while (!queue.isEmpty()) {
89 int[] curr = queue.poll();
90 int row = curr[0], col = curr[1];
91
92 if (board[row][col] != 'O') continue;
93 board[row][col] = 'T';
94
95 for (int[] dir : dirs) {
96 int newRow = row + dir[0];
97 int newCol = col + dir[1];
98 if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
99 board[newRow][newCol] == 'O') {
100 queue.offer(new int[]{newRow, newCol});
101 }
102 }
103 }
104
105 // Capture and restore
106 for (int i = 0; i < m; i++) {
107 for (int j = 0; j < n; j++) {
108 if (board[i][j] == 'O') {
109 board[i][j] = 'X';
110 } else if (board[i][j] == 'T') {
111 board[i][j] = 'O';
112 }
113 }
114 }
115 }
116}
117
118/**
119 * Iterative DFS solution using explicit stack
120 */
121class SolutionIterativeDFS {
122 public void solve(char[][] board) {
123 if (board == null || board.length == 0) return;
124
125 int m = board.length;
126 int n = board[0].length;
127 int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
128
129 // Helper method for iterative DFS
130 for (int j = 0; j < n; j++) {
131 if (board[0][j] == 'O') markSafe(board, 0, j, m, n, dirs);
132 if (board[m - 1][j] == 'O') markSafe(board, m - 1, j, m, n, dirs);
133 }
134 for (int i = 0; i < m; i++) {
135 if (board[i][0] == 'O') markSafe(board, i, 0, m, n, dirs);
136 if (board[i][n - 1] == 'O') markSafe(board, i, n - 1, m, n, dirs);
137 }
138
139 // Capture and restore
140 for (int i = 0; i < m; i++) {
141 for (int j = 0; j < n; j++) {
142 board[i][j] = board[i][j] == 'T' ? 'O' : 'X';
143 }
144 }
145 }
146
147 private void markSafe(char[][] board, int row, int col, int m, int n, int[][] dirs) {
148 Stack<int[]> stack = new Stack<>();
149 stack.push(new int[]{row, col});
150 board[row][col] = 'T';
151
152 while (!stack.isEmpty()) {
153 int[] curr = stack.pop();
154 int r = curr[0], c = curr[1];
155
156 for (int[] dir : dirs) {
157 int newR = r + dir[0], newC = c + dir[1];
158 if (newR >= 0 && newR < m && newC >= 0 && newC < n &&
159 board[newR][newC] == 'O') {
160 board[newR][newC] = 'T';
161 stack.push(new int[]{newR, newC});
162 }
163 }
164 }
165 }
166}
167