130. Surrounded Regions

https://leetcode.com/problems/surrounded-regions/

Solution:
May use the breadth first search strategy. And the search will be easier if it starts from the edges towards the inside. A visit matrix will be used to track the position visited (an alternative way is to set value of the board[i][j] that can not be surrounded from 'O' to be some other value rather than 'O' or 'X').

Code:

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int m = board.size();
        if(!m) return;
        int n = board.front().size();
        if(!n) return;
        vector<vector<bool>> visit(m, vector<bool>(n, false));
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(board[i][j] == 'O' && !visit[i][j] && (i == 0 || i == m-1 || j == 0 || j == n-1))
                    sBSF(board, i, j, visit);
            }
        }
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(!visit[i][j] && board[i][j] == 'O') board[i][j] = 'X'; 
            }
        }
    }
private:
    void sBSF(vector<vector<char>> &b, int x, int y, vector<vector<bool>> &v){
        v[x][y] = true;
        queue<pair<int, int>> q; //for BSF;
        q.push(make_pair(x, y));
        while(q.size()){
            int x1 = q.front().first; //need to updated for each loop;
            int y1 = q.front().second; //same here;
            q.pop(); 
            if(x1-1>=0 && b[x1-1][y1] == 'O' && !v[x1-1][y1]){//left;
                v[x1-1][y1] = true;
                q.push(make_pair(x1-1, y1));
            }
            if(x1+1<b.size() && b[x1+1][y1] == 'O' && !v[x1+1][y1]){//right;
                v[x1+1][y1] = true;
                q.push(make_pair(x1+1, y1));
            } 
            if(y1-1>=0 && b[x1][y1-1] == 'O' && !v[x1][y1-1]){//up;
                v[x1][y1-1] = true;
                q.push(make_pair(x1, y1-1));
            } 
            if(y1+1<b.front().size() && b[x1][y1+1] == 'O' && !v[x1][y1+1]){//down;
                v[x1][y1+1] = true;
                q.push(make_pair(x1, y1+1));
            }
        }
    }
};