You are given an m x n
matrix board
containing letters 'X'
and 'O'
, capture regions that are surrounded:
'O'
cell.'X'
cells if you can connect the region with 'X'
cells and none of the region cells are on the edge of the board
.To capture a surrounded region, replace all 'O'
s with 'X'
s in-place within the original board. You do not need to return anything.
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:
In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.
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'
.Given an m x n
matrix board
containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in-place.
A region is surrounded if it's not connected to an 'O' on the border of the board.
This approach uses DFS to identify and mark 'O's that are connected to the border. These 'O's remain as 'O's; all other 'O's are flipped to 'X's.
Algorithm:
Time Complexity: O(M*N), where M and N are the dimensions of the board. We traverse the board twice.
Space Complexity: O(M*N) in the worst case. This is due to the recursive call stack of the DFS, which could reach a depth proportional to the size of the board if the board consists only of 'O's.
Code (Python):
def solve(board):
if not board:
return
m, n = len(board), len(board[0])
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'O':
return
board[i][j] = '.' # Mark as connected to border
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
# Mark border O's
for i in range(m):
dfs(i, 0)
dfs(i, n - 1)
for j in range(n):
dfs(0, j)
dfs(m - 1, j)
# Flip remaining O's
for i in range(m):
for j in range(n):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == '.':
board[i][j] = 'O'
Code (Java):
class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0) return;
int m = board.length, n = board[0].length;
for (int i = 0; i < m; i++) {
dfs(board, i, 0);
dfs(board, i, n - 1);
}
for (int j = 0; j < n; j++) {
dfs(board, 0, j);
dfs(board, m - 1, j);
}
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';
}
}
}
private void dfs(char[][] board, int i, int j) {
int m = board.length, n = board[0].length;
if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') return;
board[i][j] = '.';
dfs(board, i + 1, j);
dfs(board, i - 1, j);
dfs(board, i, j + 1);
dfs(board, i, j - 1);
}
}
Other languages would follow a similar structure, employing recursive DFS to explore connected components.
BFS can be used instead of DFS; the algorithm remains essentially the same, replacing the recursive calls with a queue-based iteration.
Time Complexity: O(M*N)
Space Complexity: O(M*N) (due to the queue)
The Union-Find data structure can efficiently determine connected components.
Algorithm:
Time Complexity: O(MNα(M*N)) where α is the inverse Ackermann function, which is very close to a constant for practical purposes.
Space Complexity: O(M*N)
(Note: Implementing a Union-Find data structure is more involved and requires more code than the DFS/BFS approach. While theoretically efficient, for the size constraints of this problem (M, N <= 200), the difference in practical performance compared to DFS/BFS might be negligible.)