Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
To solve this problem, we can find those 'O' that is not in the surrounded first and then the remaining parts are in surrounded regions. To achieve this, we can start from the boarder line of the matrix and perform a BFS to find all 'O' that can be reached from the 'O' on boarder line.
C++ Code:
/*
* func: surrounded_region
* goal: find all regions surrounded by 'X'
* @param board: check board
* return:
*/
/*
* find all the 'O' that can be reached from 'O' on boarder line.
* Then the remaining is surrounded.
* complexity: time O(n^2), space O(n^2)
*/
void surrounded_region(vector<vector<char> > &board){
if(board.size() <= 2){
return;
}
size_t board_size_row = board.size();
size_t board_size_column = board[0].size();
queue<pair<int, int> > BFS_helper;
//Find 'O' in row boarder line
for(int column = 0; column < board_size_column; ++column){
if(board[0][column] == 'O'){
board[0][column] = 'N';
BFS_helper.emplace(pair<int, int>{0, column});
}
if(board[board_size_row-1][column] == 'O'){
board[board_size_row-1][column] = 'N';
BFS_helper.emplace(pair<int, int>{board_size_row-1, column});
}
}
//Find 'O' in column boarded line
for(int row = 0; row < board_size_row; ++row){
if(board[row][0] == 'O'){
board[row][0] = 'N';
BFS_helper.emplace(pair<int, int>{row, 0});
}
if(board[row][board_size_column-1] == 'O'){
board[row][board_size_column-1] = 'N';
BFS_helper.emplace(pair<int, int>{row, board_size_column-1});
}
}
//Use a queue to do BFS
while(!BFS_helper.empty()){
pair<int, int> current = BFS_helper.front();
BFS_helper.pop();
if(current.first > 0 && board[current.first-1][current.second] == 'O'){
board[current.first-1][current.second] = 'N';
BFS_helper.emplace(pair<int, int>{current.first-1, current.second});
}
if(current.first < board_size_row-1 && board[current.first+1][current.second] == 'O'){
board[current.first+1][current.second] = 'N';
BFS_helper.emplace(pair<int, int>{current.first+1, current.second});
}
if(current.second > 0 && board[current.first][current.second-1] == 'O'){
board[current.first][current.second-1] = 'N';
BFS_helper.emplace(pair<int, int>{current.first, current.second-1});
}
if(current.second < board_size_column-1 && board[current.first][current.second+1] == 'O'){
board[current.first][current.second+1] = 'N';
BFS_helper.emplace(pair<int, int>{current.first, current.second+1});
}
}
for(int row = 0; row < board_size_row; ++row){
for(int column = 0; column < board_size_column; ++column){
if(board[row][column] == 'O'){
board[row][column] = 'X';
}
if(board[row][column] == 'N'){
board[row][column] = 'O';
}
}
}
}
Python Code:
# func: find all regions surrounded by 'X'
# @param board: input board
# @return:
# complexity: time O(n^2), space O(n^2)
def surrounded_region(board):
if len(board) <= 2:
return
row_top = board[0]
row_bottom = board[len(board)-1]
column_left = [row[0] for row in board]
column_right = [row[len(row)-1] for row in board]
queue = []
for i in xrange(len(row_top)):
if row_top[i] == 'O':
board[0][i] = 'N'
queue.append((0, i))
if row_bottom[i] == 'O':
board[-1][i] = 'N'
queue.append((len(board)-1, i))
for j in xrange(len(column_left)):
if column_left[j] == 'O':
board[j][0] = 'N'
queue.append((j, 0))
if column_right[j] == 'O':
board[j][-1] = 'N'
queue.append((j, len(board[0])-1))
while queue:
x_curr, y_curr = queue.pop(0)
if x_curr - 1 > 0 and board[x_curr-1][y_curr] == 'O':
board[x_curr-1][y_curr] = 'N'
queue.append((x_curr-1, y_curr))
if x_curr + 1 < len(board) and board[x_curr+1][y_curr] == 'O':
board[x_curr+1][y_curr] = 'N'
queue.append((x_curr+1, y_curr))
if y_curr - 1 > 0 and board[x_curr][y_curr-1] == 'O':
board[x_curr][y_curr-1] = 'N'
queue.append((x_curr, y_curr-1))
if y_curr + 1 < len(board[0]) and board[x_curr][y_curr+1] == 'O':
board[x_curr][y_curr+1] = 'N'
queue.append((x_curr, y_curr+1))
for i in xrange(len(board)):
for j in xrange(len(board[0])):
if board[i][j] == 'O':
board[i][j] = 'X'
if board[i][j] == 'N':
board[i][j] = 'O'
