Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally&nbsp;surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

&nbsp;
Example 1:

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Notice that an 'O' should not be flipped if:
- It is on the border, or
- It is adjacent to an 'O' that should not be flipped.
The bottom 'O' is on the border, so it is not flipped.
The other three 'O' form a surrounded region, so they are flipped.


Example 2:

Input: board = [["X"]]
Output: [["X"]]


&nbsp;
Constraints:


	m == board.length
	n == board[i].length
	1 &lt;= m, n &lt;= 200
	board[i][j] is 'X' or 'O'.


# The question is an awesome example of multi-source bfs.
# The intuition is to add the boundary to a heap if it is 'O'.
# Start the bfs from the nodes added and since you're using queue(FIFO) this bfs will check for inner matrix elements and if they are also 'O' just start
# convertin all these 'O's to 'E's. 
# The last step is to traverse the matrix and if the element is still 'O' turn it to 'X' if it is 'E' turn it to 'O' and we get our answer.
# Pro-Tip -> Try to reduce the number of append operations in python. The lesser the append operations the better is the runtime!
from collections import deque
class Solution:
    def solve(self, bb: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        heap = deque()
        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        r, c = len(bb), len(bb[0])
        for i in range(r):
            if bb[i][0] == 'O': heap.append((i, 0))
            if bb[i][c - 1] == 'O': heap.append((i, c - 1))
        for i in range(1, c - 1):
            if bb[0][i] == 'O': heap.append((0, i))
            if bb[r - 1][i] == 'O': heap.append((r - 1, i))
        visited = set()
        def isValid(nr, nc):
            if 0 <= nr < r and 0 <= nc < c: return True
            else: return False
        while heap:
            ri, ci = heap.popleft()
            bb[ri][ci] = 'E'
            for i, j in directions:
                nr, nc = ri + i, ci + j
                if isValid(nr, nc) and (nr, nc) not in visited and bb[nr][nc] == 'O':
                    heap.append((nr, nc))
                    visited.add((nr, nc))
        for i in range(r):
            for j in range(c):
                if bb[i][j] == 'O':
                    bb[i][j] = 'X'
                if bb[i][j] == 'E':
                    bb[i][j] = 'O'
            
class Solution {
        boolean isClosed = true;

    public void solve(char[][] board) {
        int m = board.length;
        int n = board[0].length;

        // To identify all those O which are adjacent and unbounded by 'X', we put a temporary value
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(board[i][j] == 'O' && (i == 0 || j == 0 || i == m-1 || j == n-1) ){
                     dfs(board, i, j);
                }
            }
        }

        // revert the temperoray value and also replace remaining O with X
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(board[i][j] == 'T') board[i][j] = 'O';
                else if(board[i][j] == 'O') board[i][j] = 'X';
            }
        }

    }

    public void dfs(char[][] board, int i, int j){
        if(i<0 || j<0 || i>= board.length || j>=board[0].length || board[i][j] != 'O') return;

        board[i][j] = 'T'; // to put a temperory mark/ to mark as visited

        dfs(board, i, j+1); // Top
        dfs(board, i, j-1); // Bottom
        dfs(board, i+1, j); // Right
        dfs(board, i-1, j); // Left
    }
}
class Solution {
public:
    int n,m; int visited[201][201] = {0};
    // Breadth First Search
    // Flood Fill Algorithm
    void bfs(vector<vector<char>>& board, int x, int y){
        queue<int> q; q.push(m*x+y);
        visited[x][y] = 1;
        int curr,i,j;
        while(!q.empty()){
            curr = q.front();
            q.pop();
            i = curr/m; j = curr%m;
            board[i][j] = 'O';
            if(i > 0 && !visited[i-1][j] && board[i-1][j] == 'C'){
                visited[i-1][j] = 1;
                q.push(m*(i-1)+j);
            }
            if(i < n-1 && !visited[i+1][j] && board[i+1][j] == 'C'){
                visited[i+1][j] = 1;
                q.push(m*(i+1)+j);
            }
            if(j > 0 && !visited[i][j-1] && board[i][j-1] == 'C'){
                visited[i][j-1] = 1;
                q.push(m*i+j-1);
            }
            if(j < m-1 && !visited[i][j+1] && board[i][j+1] == 'C'){
                visited[i][j+1] = 1;
                q.push(m*i+j+1);
            }
        }
    }
    void solve(vector<vector<char>>& board) {
        n = board.size(); m = board[0].size();
        // Marking the regions to capture
        // mark all the O to C
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(board[i][j] == 'O') board[i][j] = 'C';
            }
        }
        // if we have found C on the outer edges, then all the connected C to it should be
        // converted to O as they can't be captured
        for(int i=0; i<m; i++){
            if(board[0][i] == 'C' && !visited[0][i]) bfs(board, 0, i);
            if(board[n-1][i] == 'C' && !visited[n-1][i]) bfs(board, n-1, i);
        }
        for(int i=1; i<n-1; i++){
            if(board[i][0] == 'C' && !visited[i][0]) bfs(board, i, 0);
            if(board[i][m-1] == 'C' && !visited[i][m-1]) bfs(board, i, m-1);
        }
        // capturing the regions
        // now remaining C can be capture
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(board[i][j] == 'C') board[i][j] = 'X';
            }
        }
    }
};
static const auto speedup =[](){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
// time O(n * m) | space O(1)

// We essentially invert this question
// Instead of looking whether an 'O' node is surrounded,
// we check if an 'O' node is on the edge (outer layer can't be surrounded)
// and check if that is connected with any other nodes 'O' nodes (top, down, left, right).
// We do no care if it is not connected to an 'O' edge node and thus never dfs for it.
var solve = function(board) {
    if (!board.length) return [];

    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            // Only dfs if an 'O' and on the edge
            if (board[i][j] === 'O' && (i === 0 || i === board.length - 1 || j === 0 || j === board[0].length - 1)) {
                dfs(i, j);
            }
        }
    }

    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (board[i][j] === 'V') {
                board[i][j] = 'O';
            } else {
                board[i][j] = 'X';
            }
        }
    }

    return board;

    function dfs(r, c) {
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] === 'X' || board[r][c] === 'V') {
            return;
        }

        board[r][c] = 'V';

        dfs(r + 1, c);
        dfs(r - 1, c);
        dfs(r, c - 1);
        dfs(r, c + 1);
    }
};
Surrounded Regions