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

 

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        if(board.size() == 0) return;
        int m = board.size(), n = board[0].size();
        for(int  i = 0; i < m; ++i) {
            bfs(i, 0, board);
            bfs(i, n-1, board);
        }
        for(int j = 1; j < n-1; ++j) {
            bfs(0, j, board);
            bfs(m-1, j, board);
        }
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if(board[i][j] == 'O') board[i][j] = 'X'; 
                else if(board[i][j] == '+') board[i][j] = 'O';
            }
        }
    }
    
    void bfs(int i, int j, vector<vector<char> > &board) {
        queue<int> q;
        visit(i, j, q, board);
        int n = board[0].size();
        while(!q.empty()) {
            int f = q.front();
            q.pop();
            int r = f / n;
            int l = f % n;
            visit(r-1, l, q, board);
            visit(r+1, l, q, board);
            visit(r, l-1, q, board);
            visit(r, l+1, q, board);
        }
    }
    
    void visit(int i, int j, queue<int> &q, vector<vector<char> > &board) {
        int m = board.size(), n = board[0].size();
        if(i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') return;
        board[i][j] = '+';
        q.push(i * n + j);
    }
};

 

 

欢迎关注微信公众号——计算机视觉：