<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:
        """
        Find surrounded regions and update board, from "O" to "X"
        Do not return anything, modify board in-place instead.

        * Surround: none of the region cells are on the edge of the board

        Example 1:
        board = [
            ["X","X","X","X"],
            ["X","O","O","X"],
            ["X","X","O","X"],
            ["X","O","X","X"]
            ]
        
        Example 2:
        board = [
            ["O","O"],
            ["O","O"]
            ]
        
        return [["O","O"],["O","O"]]

        Example 3:
        board = [
            ["O","O","O"],
            ["O","O","O"],
            ["O","O","O"]
            ]

        return 
        """
        m = len(board)
        n = len(board[0])
        regions = set()
        board2 = copy.deepcopy(board)

        def makeRegion(row, col):
            if row < 0 or row >=m or col < 0 or col >= n or board2[row][col] != "O":
                return
            
            curr_region.append((row, col))
            board2[row][col] = "R"

            makeRegion(row-1, col)
            makeRegion(row+1, col)
            makeRegion(row, col-1)
            makeRegion(row, col+1)

        # Find regions
        for row in range(m):
            for col in range(n):
                curr_region = []
                makeRegion(row, col)
                regions.add(tuple(curr_region))

        # Edge detections
        exclude = []
        for region in regions:
            for (row, col) in region:
                if row in [0, m-1] or col in [0,n-1]:
                    exclude.append(region)

        for region in regions:
            if region not in exclude:
                for (row, col) in region:
                    board[row][col] = "X"


        
26390