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

## Solution : (BFS)

**Approach:**\
**Iterate all the edges and mark all the '0' connected with the edges**\
**Mark all the rest '0' as 'X'**

```cpp
class Solution
{
public:
    void bfs(vector<vector<char>> &board, int a, int b)
    {
        int n = board.size();
        int m = board[0].size();

        queue<pair<int, int>> q;
        board[a][b] = '1';
        q.push({a, b});

        while (!q.empty())
        {
            int i = q.front().first;
            int j = q.front().second;
            q.pop();

            if (j - 1 >= 0 && board[i][j - 1] == 'O')
            {
                q.push({i, j - 1});
                board[i][j - 1] = '1';
            }

            if (j + 1 <= m - 1 && board[i][j + 1] == 'O')
            {
                q.push({i, j + 1});
                board[i][j + 1] = '1';
            }
            if (i - 1 >= 0 && board[i - 1][j] == 'O')
            {
                q.push({i - 1, j});
                board[i - 1][j] = '1';
            }
            if (i + 1 <= n - 1 && board[i + 1][j] == 'O')
            {
                q.push({i + 1, j});
                board[i + 1][j] = '1';
            }
        }
        return;
    }
    void solve(vector<vector<char>> &board)
    {

        int n = board.size();
        if (n == 0)
        {
            return;
        }
        int m = board[0].size();

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (i == 0 || j == 0 || i == n - 1 || j == m - 1)
                {
                    if (board[i][j] == 'O')
                    {
                        bfs(board, i, j);
                    }
                }
            }
        }

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (board[i][j] == '1')
                {
                    board[i][j] = 'O';
                }

                else if (board[i][j] == 'O')
                {
                    board[i][j] = 'X';
                }
            }
        }

        return;
    }
};
```

**Time Complexity: O(N \* M)**