<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.
        """
        def checking(row, col):
            #print("checking in: ", row, "," ,col)
            if board[row][col] == "X" or checked.get((row, col)) == "True":
                return True
            if checked.get((row, col)) == "False" or row == 0 or row == (m - 1) or col == 0 or col == (n - 1):
                return False
            checked[(row, col)] = "Checked"
            #print("checked[(row, col)] = ", checked[(row, col)])

            up, right, down, left = True, True, True, True
            #print(row - 1, "," ,col, " = ", checked.get((row - 1, col))) 
            if checked.get((row - 1, col)) != "Checked":
                up = checking(row - 1, col)
            if checked.get((row + 1, col)) != "Checked":
                down = checking(row + 1, col)
            if checked.get((row, col - 1)) != "Checked":
                left = checking(row, col - 1)
            if checked.get((row, col + 1)) != "Checked":
                right = checking(row, col + 1)
            if not (up and down and right and left):
                checked[(row, col)] = "False"
                return False
            checked[(row, col)] = "True"
            return True

        def paint(row, col):
            if board[row][col] == "X":
                return
            board[row][col] = "X"
            if row - 1 > 0:
                paint(row - 1, col)
            if row + 1 < m - 1:
                paint(row + 1, col)
            if col - 1 > 0:
                paint(row, col - 1)
            if col + 1 < n - 1:
                paint(row, col + 1)

        m = len(board)
        n = len(board[0])
        if m * n <= 8: return

        checked = {}

        for i in range(1, m - 1):
            for j in range(1, n - 1):
                if (i, j) not in checked:
                    if board[i][j] == "O":
                        if checking(i, j):
                            paint(i, j)
29450