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.

Use Breadth First Search

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';
            }
        }
    }
};