# 130. Surrounded Regions (Medium)

## 1.問題

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

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LITbple1DD8oqgsMDoS%2F-LIU8xYk2GhowLG71Ng1%2F2018072802.jpg?alt=media\&token=15db8e34-e548-4646-a9d5-fa5b01d58b62)

## 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

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LITbple1DD8oqgsMDoS%2F-LIUD8b-Bu3j10Ls9L7J%2F2018072803.jpg?alt=media\&token=2c2c71e4-dd42-40e1-a7d8-3a7521922cfe)