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

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        ROWS, COLS = len(board), len(board[0])
        visit = set()
        
        for row in range(ROWS):
            for col in range(COLS):
                if board[row][col] == "O" and (row, col) not in visit:
                    region = deque()
                    self.find_region(row, col, board, visit, region)
                    self.surround_region(region, board)
        return 

    def surround_region(self, region, board):
        buffer = region.copy()
        can_surrounded = True
        while region:
            row, col = region.popleft()
            if not self.can_surrounded(row, col, board):
                can_surrounded = False
                break
        
        if can_surrounded:
            while buffer:
                row, col = buffer.popleft()
                board[row][col] = 'X'

    def can_surrounded(self, row, col, board):
        ROWS, COLS = len(board), len(board[0])
        up = down = left = right = False
        
        ur = row
        # up direction 
        for ur in range(ur-1, -1, -1):
            if board[ur][col] == 'X':
                up = True
                break 
        
        dr = row
        # down direction
        for dr in range(dr+1, ROWS):
            if board[dr][col] == 'X':
                down = True
                break
        
        lc = col
        # left direction
        for lc in range(lc-1, -1, -1):
            if board[row][lc] == 'X':
                left = True
                break
        
        rc = col
        # right direction
        for rc in range(rc+1, COLS):
            if board[row][rc] == 'X':
                right = True
                break
        
        return left & right & up & down
    
    def find_region(self, row, col, board, visit, nodes):
        if (
            min(row, col) < 0 or
            (row, col) in visit or
            row >= len(board) or
            col >= len(board[0]) or
            board[row][col] == 'X'
        ):
            return
        nodes.append((row,col))
        visit.add((row,col))
        self.find_region(row + 1, col, board, visit, nodes)
        self.find_region(row - 1 , col, board, visit, nodes)
        self.find_region(row , col + 1, board, visit, nodes)
        self.find_region(row , col - 1, board, visit, nodes)
        return
        
        
31250