Description:
You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:
- Connect: A cell is connected to adjacent cells horizontally or vertically.
- Region: To form a region connect every
'O'cell. - Surround: The region is surrounded with
'X'cells if you can connect the region with'X'cells and none of the region cells are on the edge of theboard.
A surrounded region is captured by replacing all 'O's with 'X's in the input matrix board.
Examples:
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"]]
Example 2:
Input: board = [["X"]]
Output: [["X"]]Solution in Python:
To solve this problem, we need to identify and mark regions of ‘O’s that are not surrounded by ‘X’s, which includes regions that are connected to the boundary of the board. We can then replace all the unmarked ‘O’s (which are surrounded) with ‘X’s.
Python
from typing import List
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
# Get dimensions of the board
if not board or not board[0]:
return
m, n = len(board), len(board[0])
def dfs(x, y):
""" Perform DFS to mark the 'O's connected to the boundary """
if x < 0 or x >= m or y < 0 or y >= n or board[x][y] != 'O':
return
# Mark the cell as visited by changing it to 'E'
board[x][y] = 'E'
# Explore all four directions
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for dx, dy in directions:
dfs(x + dx, y + dy)
# Start DFS from the 'O's on the boundary
for i in range(m):
dfs(i, 0) # Left boundary
dfs(i, n - 1) # Right boundary
for j in range(n):
dfs(0, j) # Top boundary
dfs(m - 1, j) # Bottom boundary
# Traverse the board to finalize the changes
for i in range(m):
for j in range(n):
if board[i][j] == 'O':
board[i][j] = 'X' # Capture surrounded regions
elif board[i][j] == 'E':
board[i][j] = 'O' # Restore the regions connected to the boundaryExplanation:
- Dimensions Check:
- First, we check if the board is empty or if the first row is empty. If either is true, we simply return as there’s nothing to process.
- Depth-First Search (DFS) Function:
- We define a helper function
dfs(x, y)to perform DFS from the given cell (x, y). - If the cell is out of bounds or not an ‘O’, we return.
- Otherwise, we mark the cell as visited by changing its value from ‘O’ to ‘E’.
- We then recursively perform DFS on all four adjacent cells (up, down, left, right).
- We define a helper function
- Start DFS from Boundary ‘O’s:
- We initiate DFS from all ‘O’s on the boundary of the board to mark all ‘O’s connected to the boundary.
- This is done by iterating over the boundary cells and calling
dfsfor each boundary ‘O’.
- Final Traversal and Modification:
- After marking the ‘O’s connected to the boundary, we traverse the entire board again.
- We change all remaining ‘O’s to ‘X’ as they are surrounded.
- We change all ‘E’s back to ‘O’ as they were initially ‘O’s connected to the boundary and should not be captured.
This approach ensures that we only capture the regions of ‘O’s that are completely surrounded by ‘X’s and not connected to the boundary.
Solution in Javascript:
JavaScript
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solve = function(board) {
// Check if the board is empty
if (!board || board.length === 0) {
return;
}
const m = board.length;
const n = board[0].length;
// Helper function to perform DFS
const dfs = (x, y) => {
if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] !== 'O') {
return;
}
// Mark the cell as visited by changing it to 'E'
board[x][y] = 'E';
// Explore all four directions
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (const [dx, dy] of directions) {
dfs(x + dx, y + dy);
}
};
// Start DFS from the 'O's on the boundary
for (let i = 0; i < m; i++) {
dfs(i, 0); // Left boundary
dfs(i, n - 1); // Right boundary
}
for (let j = 0; j < n; j++) {
dfs(0, j); // Top boundary
dfs(m - 1, j); // Bottom boundary
}
// Traverse the board to finalize the changes
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (board[i][j] === 'O') {
board[i][j] = 'X'; // Capture surrounded regions
} else if (board[i][j] === 'E') {
board[i][j] = 'O'; // Restore the regions connected to the boundary
}
}
}
};Solution in Java:
Java
class Solution {
public void solve(char[][] board) {
// Check if the board is empty
if (board == null || board.length == 0) {
return;
}
int m = board.length;
int n = board[0].length;
// Start DFS from the 'O's on the boundary
for (int i = 0; i < m; i++) {
dfs(board, i, 0); // Left boundary
dfs(board, i, n - 1); // Right boundary
}
for (int j = 0; j < n; j++) {
dfs(board, 0, j); // Top boundary
dfs(board, m - 1, j); // Bottom boundary
}
// Traverse the board to finalize the changes
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X'; // Capture surrounded regions
} else if (board[i][j] == 'E') {
board[i][j] = 'O'; // Restore the regions connected to the boundary
}
}
}
}
// DFS helper function to mark connected 'O's
private void dfs(char[][] board, int x, int y) {
int m = board.length;
int n = board[0].length;
if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') {
return;
}
board[x][y] = 'E';
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int[] dir : directions) {
dfs(board, x + dir[0], y + dir[1]);
}
}
}Solution in C#:
C#
public class Solution {
public void Solve(char[][] board) {
// Check if the board is empty
if (board == null || board.Length == 0) {
return;
}
int m = board.Length;
int n = board[0].Length;
// Start DFS from the 'O's on the boundary
for (int i = 0; i < m; i++) {
Dfs(board, i, 0); // Left boundary
Dfs(board, i, n - 1); // Right boundary
}
for (int j = 0; j < n; j++) {
Dfs(board, 0, j); // Top boundary
Dfs(board, m - 1, j); // Bottom boundary
}
// Traverse the board to finalize the changes
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X'; // Capture surrounded regions
} else if (board[i][j] == 'E') {
board[i][j] = 'O'; // Restore the regions connected to the boundary
}
}
}
}
// DFS helper method to mark connected 'O's
private void Dfs(char[][] board, int x, int y) {
int m = board.Length;
int n = board[0].Length;
if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') {
return;
}
// Mark the cell as visited by changing it to 'E'
board[x][y] = 'E';
// Explore all four directions
int[][] directions = new int[][] {
new int[] {1, 0}, // down
new int[] {-1, 0}, // up
new int[] {0, 1}, // right
new int[] {0, -1} // left
};
foreach (var dir in directions) {
Dfs(board, x + dir[0], y + dir[1]);
}
}
}