Surrounded Regions

Surrounded RegionsFeb 22

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

Idea: BFS

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (board.size() <= 1) return;
        int rows = board.size();
        int cols = board[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        vector<vector<bool>> checked(rows, vector<bool>(cols, false));
        
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (!visited[i][j]) {
                    if (board[i][j] == 'O') {
                        if (checkIfSurrounded(i, j, board, visited, checked)) {
                            markChecked(i, j, board, checked);
                        }
                    }
                    else {
                        visited[i][j] = true;
                    }
                }
            }
        }
    }
    
    bool checkIfSurrounded(int i, int j, vector<vector<char>> &board,
        vector<vector<bool>> &visited, vector<vector<bool>> &checked) {
        queue<Pos> q;
        bool result = true;
        
        q.push(Pos(i, j));
        visited[i][j] = true;
        
        while (!q.empty()) {
            Pos pos = q.front();
            q.pop();
            i = pos.row;
            j = pos.col;
            checked[i][j] = true;
            
            if (j - 1 >= 0) {
                if (board[i][j - 1] == 'O' && !visited[i][j - 1]) {
                    q.push(Pos(i, j - 1));
                    visited[i][j - 1] = true;
                }
            }
            else {
                result = false;
            }
            
            if (j + 1 < board[0].size()) {
                if (board[i][j + 1] == 'O' && !visited[i][j + 1]) {
                    q.push(Pos(i, j + 1));
                    visited[i][j + 1] = true;
                }
            }
            else {
                result = false;
            }
            
            if (i + 1 < board.size()) {
                if (board[i + 1][j] == 'O' && !visited[i + 1][j]) {
                    q.push(Pos(i + 1, j));
                    visited[i + 1][j] = true;
                }
            }
            else {
                result = false;
            }
            
            if (i - 1 >= 0) {
                if (board[i - 1][j] == 'O' && !visited[i - 1][j]) {
                    q.push(Pos(i - 1, j));
                    visited[i - 1][j] = true;
                }
            }
            else {
                result = false;
            }
        }

        return result;
    }
    
    void markChecked(int i, int j, vector<vector<char>> &board,
        vector<vector<bool>> &checked) {
        queue<Pos> q;
        bool result = true;
        
        q.push(Pos(i, j));
        
        while (!q.empty()) {
            Pos pos = q.front();
            q.pop();
            i = pos.row;
            j = pos.col;
            
            board[i][j] = 'X';
            checked[i][j] = false;
            
            if (j - 1 >= 0) {
                if (checked[i][j - 1]) {
                    q.push(Pos(i, j - 1));
                    checked[i][j - 1] = false;
                }
            }
            
            if (j + 1 < board[0].size()) {
                if (checked[i][j + 1]) {
                    q.push(Pos(i, j + 1));
                    checked[i][j + 1] = false;
                }
            }
            
            if (i + 1 < board.size()) {
                if (checked[i + 1][j]) {
                    q.push(Pos(i + 1, j));
                    checked[i + 1][j] = false;
                }
            }
            
            if (i - 1 >= 0) {
                if (checked[i - 1][j]) {
                    q.push(Pos(i - 1, j));
                    checked[i - 1][j] = false;
                }
            }
        }
    }
    
    typedef struct Pos {
        int row, col;
        Pos(int i, int j): row(i), col(j) {};
    };
};