Surrounded Region -- Leetcode

Question:

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

Answer:
Similar to "Blood Fill" method used in computer game and graphics.

1. DFS (Recursion method), can pass small data set, but time exceeded for large set:
1.1 Directly find 'O', reverse into 'X', then DFS, if there exists an 'O' in corner in this DFS process, then backtrack to 'O'.
class Solution {
public:
    void solve(vector<vector<char>> &board) {
        if(!board.size())return;
     
        int m= board.size();
        int n= board[0].size();
        for(int i=0; i<m; ++i){
            for(int j= 0; j<n; ++j){
                if(board[i][j]=='O'){
                    DFS(i,j,board);
                }
            }
        }
        return;
    }
    bool DFS(int i, int j,vector<vector<char>> &board){
        int m= board.size();
        int n= board[0].size();
        if(i-1<0 || j-1<0 || i+1>m-1 || j+1>n-1) return false;   //corner case: 'O'
     
        board[i][j]= 'X';
     
        if(i-1>=0 && board[i-1][j]=='O'){
            if(!DFS(i-1,j,board)){
                board[i-1][j]= 'O';                      //Backtrack!!!
                return false;
            }
        }
        if(j-1>=0 && board[i][j-1]=='O'){
            if(!DFS(i,j-1,board)){
                board[i][j]= 'O';
                return false;
            }
        }
        if(i+1<=m-1 && board[i+1][j]=='O'){
            if(!DFS(i+1,j,board)){
                board[i][j]= 'O';
                return false;
            }
        }
        if(j+1<=n-1 && board[i][j+1]=='O'){
            if(!DFS(i,j+1,board)){
                board[i][j]= 'O';
                return false;
            }
        }
        return true;
    }
};

1.2 Find 'O' in the edge firstly, then DFS these "invalid" 'O's, mark them as 'C'. Finally reverse all 'O' into 'X', 'C' into 'O'.
class Solution {
public:
    void solve(vector<vector<char>> &board) {
        if(!board.size())return;
     
        int m= board.size();
        int n= board[0].size();
        for(int i=0; i<m; ++i){
            if(board[i][0]=='O')
                DFS(i,0,board);
            if(board[i][n-1]=='O')
                DFS(i,n-1,board);
        }
        for(int i=0; i<n; ++i){
            if(board[0][i]=='O')
                DFS(0,i,board);
            if(board[m-1][i]=='O')
                DFS(m-1,i,board);
        }
     
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(board[i][j]=='O')
                    board[i][j]= 'X';
                else if(board[i][j]=='C')
                    board[i][j]= 'O';
            }
        }
        return;
    }
    void DFS(int i, int j,vector<vector<char>> &board){            //Mark all corner 'O' into 'C'.
        int m= board.size();
        int n= board[0].size();
     
        board[i][j]= 'C';
     
        if(i-1>=0 && board[i-1][j]=='O')
            DFS(i-1,j,board);
        if(j-1>=0 && board[i][j-1]=='O')
            DFS(i,j-1,board);
        if(i+1<=m-1 && board[i+1][j]=='O')
            DFS(i+1,j,board);
        if(j+1<=n-1 && board[i][j+1]=='O')
            DFS(i,j+1,board);
        return;
    }
};

2. BFS: Using queue, iterative, no recursion, can pass large set.
class Solution {
    struct pair{
        int x,y;
        pair(int i,int j):x(i),y(j){};
    };
public:
    void solve(vector<vector<char>> &board) {
        if(!board.size())return;
     
        int m= board.size();
        int n= board[0].size();
     
        for(int i=0; i<m; ++i){        //For 'O' in edge case.
            if(board[i][0]=='O'){
                BFS(i,0,board);
            }
            if(board[i][n-1]=='O'){
                BFS(i,n-1,board);
            }
        }
        for(int i=0; i<n; ++i){
            if(board[0][i]=='O'){
                BFS(0,i,board);
            }
            if(board[m-1][i]=='O'){
                BFS(m-1,i,board);
            }
        }
     
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(board[i][j]=='O')         //which 'O' should be flipped to 'X'.
                    board[i][j]= 'X';
                else if(board[i][j]=='C')    //which 'O' shouldn't be flipped.
                    board[i][j]= 'O';
            }
        }
        return;
    }
    void BFS(int a,int b,vector<vector<char>> &board){        //Mark all corner 'O' into 'C'.
        int m= board.size();
        int n= board[0].size();
        queue<pair> que;
     
        board[a][b]= 'C';
        que.push(pair(a,b));
     
        while(!que.empty()){
            pair t= que.front();
            que.pop();
            int i= t.x;
            int j= t.y;
            if(i-1>=0 && board[i-1][j]=='O'){
                board[i-1][j]= 'C';
                que.push(pair(i-1,j));
            }
            if(j-1>=0 && board[i][j-1]=='O'){
                board[i][j-1]= 'C';
                que.push(pair(i,j-1));
            }
            if(i+1<=m-1 && board[i+1][j]=='O'){
                board[i+1][j]= 'C';
                que.push(pair(i+1,j));
            }
            if(j+1<=n-1 && board[i][j+1]=='O'){
                board[i][j+1]= 'C';
                que.push(pair(i,j+1));
            }
        }
        return;
    }
};