class Solution:
def solve(self, board):
if not board or not board[0]:
return
rows, cols = len(board), len(board[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != 'O':
return
board[r][c] = 'E'
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
# 1. Mark border-connected 'O's
for i in range(rows):
dfs(i, 0)
dfs(i, cols - 1)
for j in range(cols):
dfs(0, j)
dfs(rows - 1, j)
# 2. Flip all remaining 'O' to 'X', and 'E' back to 'O'
for i in range(rows):
for j in range(cols):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == 'E':
board[i][j] = 'O'
class Solution {
public:
void solve(vector<vector<char>>& board) {
int rows = board.size();
if (rows == 0) return;
int cols = board[0].size();
function<void(int, int)> dfs = [&](int r, int c) {
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != 'O')
return;
board[r][c] = 'E';
dfs(r+1, c);
dfs(r-1, c);
dfs(r, c+1);
dfs(r, c-1);
};
// 1. Mark border-connected 'O's
for (int i = 0; i < rows; ++i) {
dfs(i, 0);
dfs(i, cols-1);
}
for (int j = 0; j < cols; ++j) {
dfs(0, j);
dfs(rows-1, j);
}
// 2. Flip all remaining 'O' to 'X', and 'E' 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';
else if (board[i][j] == 'E')
board[i][j] = 'O';
}
}
}
};
class Solution {
public void solve(char[][] board) {
int rows = board.length;
if (rows == 0) return;
int cols = board[0].length;
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);
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (board[i][j] == 'O')
board[i][j] = 'X';
else if (board[i][j] == 'E')
board[i][j] = 'O';
}
}
}
private void dfs(char[][] board, int r, int c) {
int rows = board.length, cols = board[0].length;
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != 'O') return;
board[r][c] = 'E';
dfs(board, r + 1, c);
dfs(board, r - 1, c);
dfs(board, r, c + 1);
dfs(board, r, c - 1);
}
}
var solve = function(board) {
if (!board || board.length === 0) return;
const rows = board.length, cols = board[0].length;
function dfs(r, c) {
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== 'O') return;
board[r][c] = 'E';
dfs(r + 1, c);
dfs(r - 1, c);
dfs(r, c + 1);
dfs(r, c - 1);
}
// 1. Mark border-connected 'O's
for (let i = 0; i < rows; i++) {
dfs(i, 0);
dfs(i, cols - 1);
}
for (let j = 0; j < cols; j++) {
dfs(0, j);
dfs(rows - 1, j);
}
// 2. Flip all remaining 'O' to 'X', and 'E' back to 'O'
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (board[i][j] === 'O') {
board[i][j] = 'X';
} else if (board[i][j] === 'E') {
board[i][j] = 'O';
}
}
}
};
You are given a 2D board of characters, where each cell is either 'X' or 'O'. The goal is 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' on all sides (up, down, left, right). Any 'O' cell that is connected to the border of the board (directly or indirectly) is not captured.
You must modify the board in-place. There is only one valid solution for each input. Do not use extra space for another board.
At first glance, you might think to check each 'O' and see if it's completely surrounded by 'X's. However, this quickly becomes complicated, especially for larger boards or regions connected to the edge.
Instead, notice that the only 'O's that should not be flipped are those connected to the border. All other 'O's are surrounded and should be flipped. So, rather than searching for surrounded regions, it's easier to mark all border-connected 'O's and leave them alone.
This shifts the problem from "finding surrounded regions" to "finding safe regions" (those connected to the border).
'O' found on the border, perform a DFS (depth-first search) or BFS (breadth-first search) to mark all connected 'O's (for example, by changing them to a temporary marker like 'E').'O' not marked is surrounded and should be flipped to 'X'.'E') back to 'O' to restore the safe regions.We use DFS for marking because it is easy to implement and does not require extra space for a queue (if recursion stack is allowed). This approach ensures we only visit each cell a constant number of times.
Consider the input board:
X X X X
X O O X
X X O X
X O X X
'O' on the border. Mark it (e.g., change to 'E').'O's are connected to (3,1), so only (3,1) is marked.'O's not marked are surrounded. Flip them to 'X'.'E' back to 'O'.
Final board:
X X X X
X X X X
X X X X
X O X X
'O' for being surrounded individually is O((mn)^2) for an m x n board, because each check could traverse the whole board.O(mn).O(1) extra (in-place), except for recursion stack which can be up to O(mn) in the worst case (if all cells are 'O').
The key insight is to focus on which 'O's are not surrounded: those connected to the border. By marking these first and then flipping the rest, we avoid complicated checks and achieve an efficient, elegant solution. This approach is easy to implement and works in-place, making it suitable for interview and real-world scenarios.