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

```cpp
// DFS
void helper(vector<vector<char> >& board, int i, int j) {
    if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != 'O') return;
    board[i][j] = '#';
    helper(board, i - 1, j);
    helper(board, i + 1, j);
    helper(board, i, j - 1);
    helper(board, i, j + 1);
}
void solve(vector<vector<char>>& board) { // time: O(m*n); space:O (m*n)
    if (board.empty() || board[0].empty()) return;
    const int m = board.size(), n = board[0].size();
    // Mark any 'O' connected to border 'O'
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && board[i][j] == 'O') helper(board, i, j);
        }
    }
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            else if (board[i][j] == '#') board[i][j] = 'O';
        }
    }
}
```

```cpp
// BFS
void solve(vector<vector<char>>& board) { // time: O(m*n); space:O (m*n)
    if (board.empty() || board[0].empty()) return;
    int m = board.size(), n = board[0].size();
    // Mark any 'O' connected to border 'O'
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i != 0 && i != m - 1 && j != 0 && j != n - 1) continue;
            if (board[i][j] != 'O') continue;
            board[i][j] = '$';
            queue<int> q{{i * n + j}};
            while (!q.empty()) {
                int t = q.front(), x = t / n, y = t % n; q.pop();
                if (x >= 1 && board[x - 1][y] == 'O') {board[x - 1][y] = '$'; q.push(t - n);}
                if (x < m - 1 && board[x + 1][y] == 'O') {board[x + 1][y] = '$'; q.push(t + n);}
                if (y >= 1 && board[x][y - 1] == 'O') {board[x][y - 1] = '$'; q.push(t - 1);}
                if (y < n - 1 && board[x][y + 1] == 'O') {board[x][y + 1] = '$'; q.push(t + 1);}
            }
        }
    }
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            if (board[i][j] == '$') board[i][j] = 'O';
        }
    }
}
```

```cpp
// BFS
void solve(vector<vector<char>>& board) { // time: O(m * n); space:O (m * n)
    if (board.empty() || board[0].empty()) return;
    const int m = board.size(), n = board[0].size();
    const vector<pair<int, int> > dirs({ {-1, 0}, {1, 0}, {0, -1}, {0, 1} });
    // Mark all 'O's connected to border 'O's to different symbol
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if ((i != 0 && i != m - 1 && j != 0 && j != n - 1) || board[i][j] != 'O') continue;
            board[i][j] = '$';
            queue<pair<int, int> > q({{i, j}});
            while (!q.empty()) {
                int x = q.front().first, y = q.front().second;
                q.pop();
                for (const pair<int, int>& dir : dirs) {
                    int new_x = x + dir.first, new_y = y + dir.second;
                    if (new_x < 0 || new_x >= m || new_y < 0 || new_y >= n || board[new_x][new_y] != 'O') continue;
                    board[new_x][new_y] = '$';
                    q.push({new_x, new_y});
                }
            }
        }
    }
    // Capture all 'O's inside and change symbol of border 'O's back to 'O'
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            else if (board[i][j] == '$') board[i][j] = 'O';
        }
    }
}
```