Problem Statement
In this challenge, you are presented with an m x n matrix called board, filled with the characters 'X' and 'O'. Your task is to modify this matrix by capturing certain regions of characters. A region in this case is defined as a group of connected 'O' cells; two cells are connected if they are adjacent either horizontally or vertically. A region is considered surrounded if all the 'O' cells in the region are enclosed entirely by 'X' cells and none of the 'O' cells in the region are on the edge of the matrix. For all such surrounded regions, you must replace all 'O's with 'X's. This transformation should occur directly within the original matrix without needing to return it.
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"]]
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.lengthn == board[i].length1 <= m, n <= 200board[i][j]is'X'or'O'.
Approach and Intuition
The solution requires understanding the dynamics of regions in the matrix and identifying the ones that are completely surrounded by 'X'. Here's the series of steps and logic applied to achieve the solution:
- Identify 'O's on the border of the matrix, since these cannot be surrounded completely. Start from these cells to mark or protect connected 'O's from being converted.
- Traverse through the border of the matrix and apply Depth-First Search (DFS) or Breadth-First Search (BFS) to mark all 'O's that are connected to the border 'O's directly or indirectly.
- Post marking the safe 'O's, iterate over the matrix to convert unmarked 'O's (which represent surrounded regions) into 'X's.
- Convert the marked 'O's back to their original state if needed.
This approach ensures that only the 'O's which are surrounded by 'X's, and not connected to any border 'O's, are converted. The edge conditions are efficiently handled by initially focusing on the edges of the matrix.
Solutions
- C++
- Java
- C
- JavaScript
- Python
class Solution {
public:
void processBoard(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return;
int totalRows = matrix.size();
int totalCols = matrix[0].size();
for (int row = 0; row < totalRows; row++) {
for (int col = 0; col < totalCols; col++) {
if (row == 0 || col == 0 || row == totalRows - 1 || col == totalCols - 1)
exploreBoundary(matrix, row, col);
}
}
for (int row = 0; row < totalRows; row++) {
for (int col = 0; col < totalCols; col++) {
if (matrix[row][col] == 'O')
matrix[row][col] = 'X';
else if (matrix[row][col] == 'E')
matrix[row][col] = 'O';
}
}
}
private:
int rowCount, colCount;
void exploreBoundary(vector<vector<char>>& matrix, int r, int c) {
if (matrix[r][c] != 'O') return;
matrix[r][c] = 'E';
if (c < colCount - 1) exploreBoundary(matrix, r, c + 1);
if (r < rowCount - 1) exploreBoundary(matrix, r + 1, c);
if (c > 0) exploreBoundary(matrix, r, c - 1);
if (r > 0) exploreBoundary(matrix, r - 1, c);
}
};
The provided C++ code defines a solution for modifying a matrix according to specific rules related to 'surrounded regions.' This process involves changing all 'O's that are not connected to the boundary of the matrix to 'X's. The code achieves this through the following steps:
First, ensure the matrix is non-empty, or the function returns immediately.
Establish the total number of rows and columns in the matrix.
Traverse the matrix boundaries (first and last rows, and first and last columns). For each 'O' found on these boundaries, initiate a depth-first search (DFS) to mark all connected 'O's as 'E' to denote they are boundary-connected and should not be flipped.
After the boundary exploration, iterate through the entire matrix:
- Change all 'O's to 'X's (these are surrounded as they were not connected to a boundary).
- Convert all 'E's back to 'O's (these were originally boundary-connected 'O's).
The exploreBoundary private method implements the DFS. It:
- Continues only if the current cell contains 'O'.
- Marks the cell as 'E'.
- Recursively explores adjacent cells (right, down, left, and up) that are within the matrix bounds and have not been modified.
This approach ensures that only 'O's fully surrounded by 'X's (both vertically and horizontally, without connection to a boundary) are converted to 'X', adhering to the problem requirements.
public class Solution {
protected Integer numRows = 0;
protected Integer numCols = 0;
public void execute(char[][] grid) {
if (grid == null || grid.length == 0) {
return;
}
this.numRows = grid.length;
this.numCols = grid[0].length;
List<Pair<Integer, Integer>> edgeCells = new LinkedList<>();
// Construct list of edge cells
for (int row = 0; row < this.numRows; ++row) {
edgeCells.add(new Pair(row, 0));
edgeCells.add(new Pair(row, this.numCols - 1));
}
for (int col = 0; col < this.numCols; ++col) {
edgeCells.add(new Pair(0, col));
edgeCells.add(new Pair(this.numRows - 1, col));
}
// Mark the escapable cells
for (Pair<Integer, Integer> cell : edgeCells) {
this.depthFirstSearch(grid, cell.first, cell.second);
}
// Modify cells based on escape status
for (int row = 0; row < this.numRows; ++row) {
for (int col = 0; col < this.numCols; ++col) {
if (grid[row][col] == 'O') grid[row][col] = 'X';
if (grid[row][col] == 'E') grid[row][col] = 'O';
}
}
}
protected void depthFirstSearch(char[][] grid, int r, int c) {
if (grid[r][c] != 'O') return;
grid[r][c] = 'E';
if (c < this.numCols - 1) this.depthFirstSearch(grid, r, c + 1);
if (r < this.numRows - 1) this.depthFirstSearch(grid, r + 1, c);
if (c > 0) this.depthFirstSearch(grid, r, c - 1);
if (r > 0) this.depthFirstSearch(grid, r - 1, c);
}
}
class Pair<U, V> {
public U first;
public V second;
public Pair(U first, V second) {
this.first = first;
this.second = second;
}
}
The given Java solution processes a 2D grid to solve the "Surrounded Regions" problem. This program operates by identifying and marking regions that are not completely surrounded by 'X'. Here's an outline of how the solution works:
- First, it handles edge cases where the grid is undefined or empty.
- It initializes number of rows and columns based on the grid's dimensions.
- It collects all cells at the grid's edges since these cannot be surrounded due to their proximity to the boundary.
- A depth-first search (DFS) is initiated from each edge cell that contains an 'O'. During the DFS, any 'O' cell connected to an edge is marked as 'E' to denote it is escapable.
- After marking escapable regions, the grid is traversed again to finalize the states:
- Every 'O' (which wasn't converted to 'E') is replaced with 'X', signifying it is surrounded.
- Every 'E' is reverted to 'O' since it was proven to be escapable.
This approach effectively mutates the grid in place, transforming all inner 'O's that are completely surrounded by 'X's, while preserving 'O's that are interconnected with the grid's boundary. This is an efficient way to solve the problem without using additional space proportional to grid size, beyond the stack space utilized in the recursion. The use of the Pair class helps to manage grid coordinates efficiently during the DFS process.
typedef struct {
int* elements;
int currentSize;
int capacity;
} Stack;
Stack* initStack(int capacity) {
Stack* newStack = calloc(1, sizeof(Stack));
newStack->elements = calloc(capacity, sizeof(int));
newStack->capacity = capacity;
return newStack;
}
void push(Stack* stack, int value) {
if (stack->currentSize >= stack->capacity) return;
stack->elements[stack->currentSize++] = value;
}
int pop(Stack* stack) {
if (stack->currentSize == 0) return -1;
return stack->elements[--stack->currentSize];
}
void depthFirstSearch(char** matrix, int numRows, int numCols, int r, int c) {
if (matrix[r][c] != 'O') return;
Stack* stack = initStack(numRows * numCols * 2);
push(stack, r);
push(stack, c);
while (stack->currentSize != 0) {
c = pop(stack);
r = pop(stack);
if (matrix[r][c] == 'O') {
matrix[r][c] = 'E';
if (c + 1 < numCols) {
push(stack, r);
push(stack, c + 1);
}
if (r + 1 < numRows) {
push(stack, r + 1);
push(stack, c);
}
if (c > 0) {
push(stack, r);
push(stack, c - 1);
}
if (r > 0) {
push(stack, r - 1);
push(stack, c);
}
}
}
}
void solve(char** board, int rows, int* cols) {
if (rows == 0 || *cols == 0) return;
int maxRows = rows, maxCols = *cols;
for (int i = 0; i < maxRows; i++)
for (int j = 0; j < maxCols; j++) {
if (i == 0 || j == 0 || i == maxRows - 1 || j == maxCols - 1)
depthFirstSearch(board, maxRows, maxCols, i, j);
}
for (int i = 0; i < maxRows; i++)
for (int j = 0; j < maxCols; j++)
if (board[i][j] == 'O')
board[i][j] = 'X';
else if (board[i][j] == 'E')
board[i][j] = 'O';
}
The provided C code is a solution for the "Surrounded Regions" problem, where the main challenge is to examine a 2D board filled with 'X' and 'O' characters and flip all 'O' characters that are not surrounded by 'X' to 'X'. Any 'O' that is on the border of the board, or connected to an 'O' on the border, should not be flipped. The code addresses this problem using a depth-first search algorithm.
The code defines a
Stackstructure to manage indices during the depth-first search (DFS) process, which avoids recursion and makes use of explicit stack data manipulation.Essential functions for stack operations, such as
initStack,push, andpop, are implemented to facilitate pushing and popping indices from the stack.The
depthFirstSearchfunction is used to perform the DFS starting from border 'O's. This function employs the stack to keep track of indices and works by marking the reachable 'O' cells as 'E' to prevent them from being flipped later.The
solvefunction integrates these components to solve the problem:- It initializes the iteration over the board.
- Calls
depthFirstSearchfrom every border cell to mark all 'O' cells connected to the borders. - Changes all unmarked 'O' cells to 'X' and all 'E' cells back to 'O' in a second pass through the board.
This approach efficiently flips the surrounded regions without modifying those connected to the boundary, ensuring correct categorization and modification of 'O' cells on the board.
var processBoard = function (gameBoard) {
if (gameBoard == null || gameBoard.length == 0) {
return;
}
let totalRows = gameBoard.length;
let totalCols = gameBoard[0].length;
let edgeCells = [];
for (let row = 0; row < totalRows; ++row) {
edgeCells.push([row, 0]);
edgeCells.push([row, totalCols - 1]);
}
for (let col = 0; col < totalCols; ++col) {
edgeCells.push([0, col]);
edgeCells.push([totalRows - 1, col]);
}
edgeCells.forEach((coords) => {
depthFirstSearch(gameBoard, coords[0], coords[1]);
});
for (let row = 0; row < totalRows; ++row) {
for (let col = 0; col < totalCols; ++col) {
if (gameBoard[row][col] == "O") gameBoard[row][col] = "X";
if (gameBoard[row][col] == "E") gameBoard[row][col] = "O";
}
}
function depthFirstSearch(board, r, c) {
if (board[r][c] != "O") return;
board[r][c] = "E";
if (c < totalCols - 1) depthFirstSearch(board, r, c + 1);
if (r < totalRows - 1) depthFirstSearch(board, r + 1, c);
if (c > 0) depthFirstSearch(board, r, c - 1);
if (r > 0) depthFirstSearch(board, r - 1, c);
}
};
This JavaScript solution tackles the problem of flipping surrounded regions on a game board from 'O' to 'X'. The given function, processBoard, accepts a gameBoard array representing the board state. The approach involves, initially identifying the edge cells of the board and then initiating a depth-first search (DFS) to mark the 'O's that are connected to these boundary 'O's with an 'E'. These are not flipped to 'X' since they're connected to an edge, indirectly meaning they're not surrounded. Post the DFS process, any 'O's left on the board, which aren't converted to 'E', are surrounded entirely by 'X's and hence are flipped to 'X'. All the 'E's are then reverted back to 'O', maintaining the integrity of the regions connected to edges. Here's a concise breakdown of how the code handles the problem:
- Initially checks if the
gameBoardis empty or null, and returns immediately if true. - Computes dimensions of the board (
totalRowsandtotalCols). - Collects all edge cell coordinates into the
edgeCellsarray. - Uses depth-first search (
depthFirstSearchfunction) originating from each edge cell to mark board cells that are linked directly to borders with 'E' to avoid flipping them later. - Iterates over the board to flip all 'O' to 'X', meaning these are truly enclosed by 'X'.
- Converts 'E' back to 'O' to restore any cells that were connected to the board's boundary and not surrounded.
This method ensures that only the regions not connected to the boundary get flipped, hence solving the problem efficiently while modifying the board in place.
class Solution:
def process(self, grid: List[List[str]]) -> None:
if not grid or not grid[0]:
return
self.maxRows = len(grid)
self.maxCols = len(grid[0])
# Gather border positions
from itertools import product
edge_cells = list(product(range(self.maxRows), [0, self.maxCols - 1])) + list(
product([0, self.maxRows - 1], range(self.maxCols))
)
# Mark the "safe" cells with placeholder 'S'
for r, c in edge_cells:
self.depthFirstSearch(grid, r, c)
# Transform 'O' to 'X' (captured) and 'S' to 'O' (safe)
for r in range(self.maxRows):
for c in range(self.maxCols):
if grid[r][c] == "O":
grid[r][c] = "X"
elif grid[r][c] == "S":
grid[r][c] = "O"
def depthFirstSearch(self, grid: List[List[str]], r: int, c: int) -> None:
if grid[r][c] != "O":
return
grid[r][c] = "S"
if c < self.maxCols - 1: self.depthFirstSearch(grid, r, c + 1)
if r < self.maxRows - 1: self.depthFirstSearch(grid, r + 1, c)
if c > 0: self.depthFirstSearch(grid, r, c - 1)
if r > 0: self.depthFirstSearch(grid, r - 1, c)
This Python solution tackles the problem of transforming a 2D grid of characters where regions surrounded by the character 'X' need to be converted. This involves two main steps:
Identifying "safe" regions that are connected to the grid's boundary and should not be flipped.
Transforming the surrounded 'O' characters into 'X' while reverting "safe" characters back to 'O'.
Use a depth-first search (DFS) approach to traverse and mark nodes.
Start by identifying all border cells that contain the character 'O' and treat these as entry points for a DFS that marks all reachable 'O' characters with a temporary marker 'S'.
Iterate through the entire grid post DFS, converting all 'S' marked nodes back to 'O', and transforming standalone 'O' nodes to 'X', thereby indicating they are surrounded.
This method is robust and ensures that only those regions truly surrounded by 'X' on all sides are flipped, while boundary-connected regions remain intact.
No comments yet.