130. Surrounded Regions

解題心得

從邊緣的 O 往內走訪，最後再回頭重新檢視誰要被翻過去。

程式碼

class Solution {
public:
    void helper(vector<vector<char>>& board, vector<vector<bool>>& notFlip, int x, int y)
    {
        if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size())
            return;
        if(board[x][y] == 'X' || notFlip[x][y])
            return;

        int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
        notFlip[x][y] = true;
        for(int i=0; i<4; i++)
        {
            helper(board, notFlip, x+dx[i], y+dy[i]);
        }
    }
    void solve(vector<vector<char>>& board) {
        vector<vector<bool>> notFlip(board.size(), vector<bool>(board[0].size(), false));
        for(int i=0; i<board.size(); i++)
        {
            for(int j=0; j<board[0].size(); j++)
            {
                if(board[i][j] == 'O' && (i == 0 || i == board.size() - 1 || j == 0 || j == board[0].size() - 1))
                {
                    helper(board, notFlip, i, j);
                }
            }
        }
        for(int i=0; i<board.size(); i++)
        {
            for(int j=0; j<board[0].size(); j++)
            {
                if(board[i][j] == 'O' && !notFlip[i][j])
                    board[i][j] = 'X';
            }
        }
    }
};