# 【LeetCode】 130. Surrounded Regions

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

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

> 給予一個二維面板包含`'X'`和`'O'` (字母 O)，佔領所有被`'X'`包圍的地區。

> 反轉所有`'O'`使其成為`'X'`來佔領一個區域。

> 解釋：
> 被佔領的區域不應該在邊界上，因此任何在邊界上的`'O'`都不應該被反轉為`'X'`。任何`'O'`不在邊界上或是沒有和邊界連接到的都會被翻轉成`'X'`。兩個格子連接是指他們水平或垂直連接。

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

## Solution

* 這一類的題目已經出現好幾次了，一看到2D面板就先想到DFS。
* 我們要做的事情是保留住從邊界上DFS遍歷到的所有`'O'`。
* 我先將`O`轉換為暫時符號`'N'`，接著DFS遍歷所有邊界上的`'N'`，將其轉回`'O'`。最後將所有沒有被遍歷到的暫時符號`'N'`轉成`'X'`。
* 注意邊界限制。

### Code

class Solution {
public:
    void dfs(vector<vector<char>>& board, int y, int x)
    {
        board[y][x] = 'O';
        if(y > 0 && board[y - 1][x] == 'N')
            dfs(board, y - 1, x);
        if(x > 0 && board[y][x - 1] == 'N')
            dfs(board, y, x - 1);
        if(y < board.size() - 1 && board[y + 1][x] == 'N')
            dfs(board, y + 1, x);
        if(x < board[0].size() - 1 && board[y][x + 1] == 'N')
            dfs(board, y, x + 1);
    }
    void solve(vector<vector<char>>& board) {
        if(board.empty()) return;
        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] = 'N';
        
        for(int i = 0; i < board.size(); i++)
        {
            if(board[i][0] == 'N') dfs(board, i, 0);
            if(board[i][board[0].size() - 1] == 'N') dfs(board, i, board[0].size() - 1);
        }
        for(int j = 0; j < board[0].size(); j++)
        {
            if(board[0][j] == 'N') dfs(board, 0, j);
            if(board[board.size() - 1][j] == 'N') dfs(board, board.size() - 1, j);
        }

        for(int i = 0; i < board.size(); i++)
            for(int j = 0; j < board[0].size(); j++)
                if(board[i][j] == 'N') board[i][j] = 'X';
    }
};

###### tags: `LeetCode` `C++`