# 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';
        }
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dfs-and-bfs/130.-surrounded-regions.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.