LeetCode: 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.

题目大意： 将给定的 "O", "X" 构成的矩阵中，被 X 包围的 O 反转为 X。

解题思路

将边界连通的 O 标记，然后将没有标记的 O 都反转为 X 即可。
如：

X O O X X
O X O O X
X O X X X
X O O O X
X X X X X

对边界连通的 O 进行标记：

X  -O -O  X X
-O  X -O -O X
X   O  X  X X
X   O  O  O X
X   X  X  X X

然后将没标记的 O 反转为 X， 并清除标记的 O 的标记。

X O O X X
O X O O X
X X X X X
X X X X X
X X X X X

AC 代码

class Solution {
private:
    // 将边界的 ‘O’ 标记
    void FlagBorder(vector<vector<char>>& board, int x, int y)
    {
        const static int dirs[][2] = {{1,0}, {0,1}, {-1, 0}, {0, -1}};

        if(board[x][y] == 'X' || board[x][y] == -'O') return;
        else board[x][y] = -'O';

        for(int i = 0; i < 4; ++i)
        {
            int tx = x + dirs[i][0];
            int ty = y + dirs[i][1];

            if(tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size())
            {
                continue;
            }

            FlagBorder(board, tx, ty);
        }
    }
public:
    void solve(vector<vector<char>>& board) {

        if(board.empty() || board[0].empty()) return;

        // 标记边界
        for(int i = 0; i < board.size(); ++i)
        {
            FlagBorder(board, i, 0);
            FlagBorder(board, i, board[0].size()-1);
        }
        for(int i = 0; i < board[0].size(); ++i)
        {
            FlagBorder(board, 0, i);
            FlagBorder(board, board.size()-1, i);
        }

        // 统计边界和非边界
        for(int i = 0; i < board.size(); ++i)
        {
            for(int j = 0; j < board[0].size(); ++j)
            {
                if(board[i][j] == 'O') board[i][j] = 'X';          // 没标记的 'O' 反转为 'X' 
                else if(board[i][j] == -'O') board[i][j] = 'O';    // 标记的 'O' 清除标记
            }
        }
    }
};