130. Surrounded Regions

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

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

Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

---

给定一个board，要求把其中被X包围的O也改为X，这里的包围必须四周全都有X。 开始的想法是，这个问题类似于找岛屿的问题，可以用BFS/DFS或者并查集，但是感觉不太好弄，比如虽然并查集能找到所有岛屿，但是要区分全包围和半包围还是有点麻烦。

查看讨论区，解法很巧妙。半包围的O肯定出现在边缘，所以我们先从边缘的O开始DFS，把所有半包围的O改为一个其他的字符，比如’1’。这样之后，剩余的所有O肯定是被X全包围的，而那些被标记为’1’的，则是原来被半包围的’O’。所以最后，我们遍历整个board，遇到’O’直接改为’X’就好，遇到’1’，则改回原来的’O’。直接O(1)空间复杂度就搞定了，不错。 代码如下：

vector<vector<int> > dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
class Solution {
private:
    int m, n;
    bool isOk(int x, int y) { return x >= 0 && x < m && y >= 0 && y < n; }
    void dfs(vector<vector<char> >& board, int x, int y)
    {
        board[x][y] = ‘1’;
        for (int i = 0; i < dirs.size(); ++i) {
            int u = x + dirs[i][0], v = y + dirs[i][1];
            if (isOk(u, v) && board[u][v] == ‘O’)
                dfs(board, u, v);
        }
    }
public:
    void solve(vector<vector<char> >& board)
    {
        if (board.empty() || board[0].empty())
            return;
        m = board.size(), n = board[0].size();
        for (int i = 0; i < m; ++i) {
            if (board[i][0] == ‘O’)
                dfs(board, i, 0);
            if (board[i][n – 1] == ‘O’)
                dfs(board, i, n – 1);
        }
        for (int j = 0; j < n; ++j) {
            if (board[0][j] == ‘O’)
                dfs(board, 0, j);
            if (board[m – 1][j] == ‘O’)
                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’;
                else if (board[i][j] == ‘1’)
                    board[i][j] = ‘O’;
            }
        }
    }
};

本代码提交AC，用时13MS。