Given a 2D board containing 'X' (representing walls) and 'O' (representing open spaces), capture all regions surrounded by 'X'. A region is considered surrounded if all its adjacent cells (top, bottom, left, and right) are walls or are out of bounds.
Replace all surrounded regions with 'X'.
Table of Contents
Sample Input:
Board:
[
['X', 'X', 'X', 'X'],
['X', 'O', 'O', 'X'],
['X', 'X', 'O', 'X'],
['X', 'O', 'X', 'X']
]
Expected Output:
[
['X', 'X', 'X', 'X'],
['X', 'X', 'X', 'X'],
['X', 'X', 'X', 'X'],
['X', 'O', 'X', 'X']
]
In this example, the surrounded regions in the board will be identified, and all regions that are surrounded by walls or out of bounds will be replaced with 'X'.
Time and Space Complexity:
The time complexity of the algorithm is O(m * n), where ‘m’ is the number of rows and ‘n’ is the number of columns in the board. We need to visit each cell once to identify the surrounded regions.
The space complexity is O(m * n) as well, due to the recursion stack, which can grow to the size of the board in the worst case.
C++ solution:
#include <iostream>
#include <vector>
void dfs(std::vector<std::vector<char>>& board, int row, int col) {
// Base case: If the current cell is out of bounds or it is not an open space ('O'), return.
if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size() || board[row][col] != 'O') {
return;
}
// Mark the current cell as visited by changing it to 'Y'.
board[row][col] = 'Y';
// Visit all adjacent cells (top, bottom, left, right) recursively.
dfs(board, row - 1, col); // Top neighbor
dfs(board, row + 1, col); // Bottom neighbor
dfs(board, row, col - 1); // Left neighbor
dfs(board, row, col + 1); // Right neighbor
}
void solve(std::vector<std::vector<char>>& board) {
int rows = board.size();
int cols = board[0].size();
// Step 1: Identify the 'O' cells connected to the boundaries and mark them as 'Y'.
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if ((i == 0 || i == rows - 1 || j == 0 || j == cols - 1) && board[i][j] == 'O') {
dfs(board, i, j);
}
}
}
// Step 2: Replace all remaining 'O's (surrounded regions) with 'X' and restore 'Y' cells 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] == 'Y') {
board[i][j] = 'O';
}
}
}
}
int main() {
// Construct the board for the sample input
std::vector<std::vector<char>> board = {
{'X', 'X', 'X', 'X'},
{'X', 'O', 'O', 'X'},
{'X', 'X', 'O', 'X'},
{'X', 'O', 'X', 'X'}
};
// Solve the surrounded regions in the board
solve(board);
// Print the result
std::cout << "Surrounded Regions Result:" << std::endl;
for (const auto& row : board) {
std::cout << "[";
for (int i = 0; i < row.size(); ++i) {
std::cout << row[i];
if (i < row.size() - 1) {
std::cout << ", ";
}
}
std::cout << "]" << std::endl;
}
return 0;
}
The dfs function is a helper function that performs a depth-first search (DFS) to visit all open spaces (‘O’) connected to a given cell. It marks all these cells as visited by changing them to ‘Y’.
The solve function is the entry point of the algorithm. It starts by identifying all open spaces (‘O’) connected to the boundaries of the board (top, bottom, left, right) and marks them as ‘Y’ using the dfs function. Then, it replaces all remaining ‘O’s (surrounded regions) with ‘X’ and restores the ‘Y’ cells back to ‘O’.
In the given example, the function will correctly solve the surrounded regions in the board, and the output will be as follows:
Surrounded Regions Result:
[X, X, X, X]
[X, X, X, X]
[X, X, X, X]
[X, O, X, X]