<p>You are given an <code>m x n</code> matrix <code>board</code> containing <strong>letters</strong> <code>&#39;X&#39;</code> and <code>&#39;O&#39;</code>, <strong>capture regions</strong> that are <strong>surrounded</strong>:</p>

<ul>
	<li><strong>Connect</strong>: A cell is connected to adjacent cells horizontally or vertically.</li>
	<li><strong>Region</strong>: To form a region <strong>connect every</strong> <code>&#39;O&#39;</code> cell.</li>
	<li><strong>Surround</strong>: The region is surrounded with <code>&#39;X&#39;</code> cells if you can <strong>connect the region </strong>with <code>&#39;X&#39;</code> cells and none of the region cells are on the edge of the <code>board</code>.</li>
</ul>

<p>A <strong>surrounded region is captured</strong> by replacing all <code>&#39;O&#39;</code>s with <code>&#39;X&#39;</code>s in the input matrix <code>board</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">board = [[&quot;X&quot;,&quot;X&quot;,&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;O&quot;,&quot;O&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;X&quot;,&quot;O&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;O&quot;,&quot;X&quot;,&quot;X&quot;]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[[&quot;X&quot;,&quot;X&quot;,&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;X&quot;,&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;X&quot;,&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;O&quot;,&quot;X&quot;,&quot;X&quot;]]</span></p>

<p><strong>Explanation:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/19/xogrid.jpg" style="width: 367px; height: 158px;" />
<p>In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">board = [[&quot;X&quot;]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[[&quot;X&quot;]]</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == board.length</code></li>
	<li><code>n == board[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>board[i][j]</code> is <code>&#39;X&#39;</code> or <code>&#39;O&#39;</code>.</li>
</ul>

B = []
m = 0
n = 0
class Solution:
    def NG(self,i,j):
        global m
        global n
        Narray = []

        U = [i-1,j]
        UE = (i-1)>=0

        D = [i+1,j]
        DE = (i+1)<m

        L = [i,j-1]
        LE = (j-1)>=0

        R = [i,j+1]
        RE = (j+1)<n

        if UE:
            Narray.append(U)
        if DE:
            Narray.append(D)
        if LE:
            Narray.append(L)
        if RE:
            Narray.append(R)
        
        return Narray

    def BFS(self,source):
        global m
        global n
        global B 
        Q = []
        V = []
        Q.append(source)
        #print(source)
        V.append(source)
        B[source[0]][source[1]]='X'
        while not len(Q)==0:
            v = Q.pop(0)
            for [x,y] in self.NG(v[0],v[1]):
                if B[x][y]=='O':
                    if (x==0 or x==(m-1) or y==0 or y==(n-1)):
                        for [a,b] in V:
                            B[a][b] = 'O'
                        return
                    else:
                        B[x][y]='X'
                        V.append([x,y])
                        Q.append([x,y])
        
        return   

    def solve(self, board: List[List[str]]) -> None:
        global m 
        global n
        global B
        """
        Do not return anything, modify board in-place instead.
        """
        m = len(board)
        n = len(board[0])
        B = board

        for i in range(1,m-1):
            for j in range(1,n-1):
                if board[i][j]=='O':
                    source=[i,j]
                    self.BFS(source)
        '''
        for i in range(m):
            for j in range(n):
                if board[i][j]=='1':
                    board[i][j] = 'X'
        '''



        
20450