# [leetcode] Surrounded Regions

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```

BFS, but the following code runs in Time Limited Excced problem.

We should find all the ‘O’ cells that are connected to the ‘O’ cells on the boundary. These ‘O’ cells are survived and not captured.

Time Limit Exceed sulution.

```//What should I return if board is NULL?
//Will the size of the board be very large? More than 2^32?
//It's just like the rules in Go.(Wei qi)
//Is the board always be a rectangular?

//BFS
class Cell{
public:
int row, column;
Cell(int i, int j): row(i), column(j){}
};
class Solution {
public:
void solve(vector<vector<char>>& board) {
//extreme cases
if(board.size() <= 1) return ;

//ordinary cases, traverse the board, find all 'O' cells
for(size_t i = 0; i < board.size(); i++){
for(size_t j = 0; j < board[0].size(); j++){
if(board[i][j] == 'O'){
BFS(board, i, j);
}
}
}
restoreBoard(board);
}
void BFS(vector<vector<char>> & board, int row, int column){
int rowSize = board.size();
int columnSize = board[0].size();
queue<Cell> q;
q.push(Cell(row, column));
board[row][column] = 'V'; //visited
while(!q.empty()){
Cell cell = q.front();
q.pop();
row = cell.row;
column = cell.column;
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
int offsetRow = i * 2 - 1;
int offsetColumn = j * 2 - 1;
int nrow = row + offsetRow;
int ncolumn = column + offsetColumn;
//out of boundary
if(nrow < 0 || nrow >= board.size() || ncolumn < 0 || ncolumn > board[0].size()){
markAsSurvive(board);
return ;
}
if(board[row][column] == 'V'){
//visited
continue;
}
if(board[nrow][ncolumn] == 'O'){
q.push(Cell(nrow, ncolumn));
board[nrow][ncolumn] = 'V';
}
}
}
}
markAsCaptured(board);
}
void markAsSurvive(vector<vector<char>> & board){
for(size_t i = 0; i < board.size(); i++){
for(size_t j = 0; j < board[0].size(); j++){
if(board[i][j] == 'V') board[i][j] = 'S';
}
}
}
void markAsCaptured(vector<vector<char>> & board){
for(size_t i = 0; i < board.size(); i++){
for(size_t j = 0; j < board[0].size(); j++){
if(board[i][j] == 'V') board[i][j] = 'X';
}
}
}
void restoreBoard(vector<vector<char>> & board){
for(size_t i = 0; i < board.size(); i++){
for(size_t j = 0; j < board[0].size(); j++){
if(board[i][j] == 'S') board[i][j] = 'O';
}
}
}
};```

AC solution

We don’t need a hash table to record visited cells, manipulate the board, mark visited cell as ‘S’ is an ingenious method.

```class Cell{
public:
int row, column;
Cell(int row, int column):row(row), column(column){}
};

class Solution {
public:
void solve(vector<vector<char>>& board) {
//extreme cases
if(board.size() == 0) return;
if(board.size() <= 1 || board[0].size() <= 1) return;

//traverse boundary cells
for(size_t i = 0; i < board.size(); i++){
BFS(board, i, 0); //left boundary
BFS(board, i, board[0].size() - 1); //right boundary
}
for(size_t i = 0; i < board[0].size(); i++){
BFS(board, 0, i); //top boundary
BFS(board, board.size() - 1, i); //bottom boundary
}
markSurviveAsO(board);
}

void BFS(vector<vector<char>> & board, int row, int column){
queue<Cell> q;
int dict[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}}; //direction
if(board[row][column] != 'O') return ;
q.push(Cell(row, column));
board[row][column] = 'S'; //survive
while(!q.empty()){
row = q.front().row;
column = q.front().column;
q.pop();
for(int i = 0; i < 4; i++){
int nrow = row + dict[i][0];
int ncolumn = column + dict[i][1];
if(nrow < 0 || nrow >= board.size() || ncolumn < 0 || ncolumn >= board[0].size()){
//out of boundary
continue;
}
if(board[nrow][ncolumn] == 'O'){
board[nrow][ncolumn] = 'S';
q.push(Cell(nrow, ncolumn));
}
}
}
}
void markSurviveAsO(vector<vector<char>> & board){
for(size_t i = 0; i < board.size(); i++){
for(size_t j = 0; j < board[0].size(); j++){
char c = board[i][j];
if(c == 'S') board[i][j] = 'O';
else board[i][j] = 'X';
}
}
}
};
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.