130. Surrounded Regions (Medium)

1.問題

• 給予一個有著'X', 'O'的2D版, 找出所有由X包圍的區域

2.想法

• 用DFS將外圍的'O'有碰到的''O都改為'A', 並掃描所有的elements, 將'A'改為'O'

3.程式碼

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if (board.size() == 0) {
            return;
        }
        int h = board.size(), w = board[0].size();
        
        for (int i = 0; i < h; i++) {
            check(board, i, 0);
            check(board, i, w - 1);
        }
        
        for (int i = 0; i < w; i++) {
            check(board, 0, i);
            check(board, h - 1, i);
        }
        
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (board[i][j] == 'A') {
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }
    }
private:
    void check(vector<vector<char>>& board, int r, int c) {
        if (r >= 0 && r < board.size() && 
            c >= 0 && c < board[0].size() &&
            board[r][c] == 'O') {
            board[r][c] = 'A';
            check(board, r + 1, c);
            check(board, r - 1, c);
            check(board, r, c + 1);
            check(board, r , c - 1);
        }
    }
};

4.Performance