Surrounded Regions [Leetcode]

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

Solution: we search the elements with a way out from the out-most layer to inside, and mark such elements as 'N's; after search, we change all 'O' to 'X' and change all 'N' to 'O'; the search can be done in either BFS or DFS fashion.

   /*******************************SOLUTION 1***********************************/

class Solution {
public:
    typedef struct point{
      int x;
      int y;
      point(int a, int b){x=a; y=b;}
    } Point;
    void solve(vector<vector<char>> &board) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(board.empty() || board[0].empty())
            return;
        int rows = board.size();
        int cols = board[0].size();
        queue<Point> q;
        //scan the first and last rows
        for(int i=0; i<cols; ++i){
            if(board[0][i]=='O'){
                q.push(Point(0,i));
                board[0][i]='N';
            }
            if(board[rows-1][i]=='O'){
                q.push(Point(rows-1, i));
                board[rows-1][i]='N';
            }
        }
        //scan the first and last colomns
        for(int i=1; i<rows-1; ++i){
            if(board[i][0]=='O'){
                q.push(Point(i, 0));
                board[i][0]='N';
            }
            if(board[i][cols-1]=='O'){
                q.push(Point(i, cols-1));
                board[i][cols-1]='N';
            }
        }
        //BFS
        while(!q.empty()){
            Point tmp = q.front();
            q.pop();
            //check surrounding cells
            if(tmp.x-1>=0 && board[tmp.x-1][tmp.y]=='O'){
                q.push(Point(tmp.x-1, tmp.y));
                board[tmp.x-1][tmp.y]='N';
            }
            if(tmp.x+1<rows && board[tmp.x+1][tmp.y]=='O'){
                q.push(Point(tmp.x+1, tmp.y));
                board[tmp.x+1][tmp.y]='N';
            }
            if(tmp.y-1>=0 && board[tmp.x][tmp.y-1]=='O'){
                q.push(Point(tmp.x, tmp.y-1));
                board[tmp.x][tmp.y-1]='N';
            }
            if(tmp.y+1<cols && board[tmp.x][tmp.y+1]=='O'){
                q.push(Point(tmp.x, tmp.y+1));
                board[tmp.x][tmp.y+1]='N';
            }
        }
        //fill the board
        for(int i=0; i<rows; ++i)
            for(int j=0; j<cols; ++j){
                if(board[i][j]=='O')
                    board[i][j]='X';
                if(board[i][j]=='N')
                    board[i][j]='O';
            }
    }
};

   /*******************************SOLUTION 2***********************************/

class Solution {
public:
    void DFS(vector<vector<char>> &board, int x, int y){
        int rows = board.size();
        int cols = board[0].size();
        if(x-1>=0 && board[x-1][y]=='O'){
            board[x-1][y]='N';
            DFS(board, x-1, y);
        }
        if(x+1<rows && board[x+1][y]=='O'){
            board[x+1][y]='N';
            DFS(board, x+1, y);
        }
        if(y-1>=0 && board[x][y-1]=='O'){
            board[x][y-1]='N';
            DFS(board, x, y-1);
        }
        if(y+1<cols && board[x][y+1]=='O'){
            board[x][y+1]='N';
            DFS(board, x, y+1);
        }
    }
    void solve(vector<vector<char>> &board) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(board.empty() || board[0].empty())
            return;
        int rows = board.size();
        int cols = board[0].size();
        //scan the first and last rows and do DFS
        for(int i=0; i<cols; ++i){
            if(board[0][i]=='O'){
                board[0][i]='N';
                DFS(board, 0, i);
            }
            if(board[rows-1][i]=='O'){
                board[rows-1][i]='N';
                DFS(board, rows-1, i);
            }
        }
        //scan the first and last colomns and do DFS
        for(int i=1; i<rows-1; ++i){
            if(board[i][0]=='O'){
                board[i][0]='N';
                DFS(board, i, 0);
            }
            if(board[i][cols-1]=='O'){
                board[i][cols-1]='N';
                DFS(board, i, cols-1);
            }
        }
        //fill the board
        for(int i=0; i<rows; ++i)
            for(int j=0; j<cols; ++j){
                if(board[i][j]=='O')
                    board[i][j]='X';
                if(board[i][j]=='N')
                    board[i][j]='O';
            }
    }
};