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.

分析：

这题目和connected region in undirected graph一样，可以用dfs或者bfs解。

但是需要注意到，这道题目有点tricky因为他说从边缘开始的的点，不算surrounded regions。所以其实题意是找到除了边缘开始的区域以外的connected region。这样的话，先做单次循环把所有边缘延伸进来的区域标记掉，再遍历一遍就可以了。

解法bfs：

class Solution {
public:
    /**
     * @param board a 2D board containing 'X' and 'O'
     * @return void
     */
    void bfs(vector<vector<char> > &board, int i, int j) {
        int m = board.size();
        int n = board[0].size();
        int code = i * n + j;
        queue<int> Q;
        Q.push(code);
        while (!Q.empty() ) {
            code = Q.front();
            Q.pop();
            int x = code / n;
            int y = code % n;
            if (board[x][y] == 'X' || board[x][y] == 'B') {
                continue;
            }
            board[x][y] = 'B';
            if (x - 1 >= 0 && board[x - 1][y] == 'O') {
                Q.push((x - 1) * n + y);
            }
            if (x + 1 < m && board[x + 1][y] == 'O') {
                Q.push((x + 1) * n + y);
            }
            if (y - 1 >= 0 && board[x][y - 1] == 'O') {
                Q.push(x * n + y - 1);
            }
            if (y + 1 < n && board[x][y + 1] == 'O') {
                Q.push(x * n + y + 1);
            }
        }
    }

    void surroundedRegions(vector<vector<char>>& board) {
        // Write your code here
        if (board.size() == 0 || board[0].size() == 0) {
            return;
        }
        int m = board.size();
        int n = board[0].size();
        for (int i = 0; i < m; i++) {
            bfs(board, i, 0);
            bfs(board, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            bfs(board, 0, j);
            bfs(board, m - 1, j);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == 'B') {
                    board[i][j] = 'O';
                }
            }
        }
    }
};

解法dfs：

class Solution {
public:
    /**
     * @param board a 2D board containing 'X' and 'O'
     * @return void
     */
    void dfs(vector<vector<char> > &board, int i, int j) {
        if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() ) {
            return;
        }
        if (board[i][j] == 'X' || board[i][j] == 'B') {
            return;
        }
        board[i][j] = 'B';
        dfs(board, i - 1, j);
        dfs(board, i + 1, j);
        dfs(board, i, j - 1);
        dfs(board, i, j + 1);
    } 

    void surroundedRegions(vector<vector<char>>& board) {
        // Write your code here
        if (board.size() == 0 || board[0].size() == 0) {
            return;
        }
        int m = board.size();
        int n = board[0].size();
        for (int i = 0; i < m; i++) {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            dfs(board, 0, j);
            dfs(board, m - 1, j);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == 'B') {
                    board[i][j] = 'O';
                }
            }
        }
    }
};