<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.
        """
        directions=[[0,1],[0,-1],[1,0],[-1,0]]
        rows,cols=len(board),len(board[0])
        def flip(r,c):
            if (r<0 or c<0 or r>=rows or c>=cols or board[r][c]!="O"):
                return
            board[r][c]="SSS"
            for dr,dc in directions:
                flip(r+dr,c+dc)

        for r in range(rows):
            for c in range(cols):
                if (r==0 or r==rows-1 or c==0 or c==cols-1) and board[r][c]=="O":
                    flip(r,c)
        for r in range(rows):
            for c in range(cols):
                if board[r][c]=="O":
                    board[r][c]="X"
        for r in range(rows):
            for c in range(cols):
                if board[r][c]=="SSS":
                    board[r][c]="O"
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        # rows,cols=len(board),len(board[0])
        # directions=[[0,1],[0,-1],[1,0],[-1,0]]
        # #如果连着边界的0，仍然会被flip
        # def flip(r,c):
        #     if (r<0 or c<0 or r>=rows or c>=cols
        #     or board[r][c]!="O"):
        #         return 
        #     board[r][c]="SSS"
        #     for dr,dc in directions:
        #         flip(r+dr,c+dc)
        # #把边界的先保护起来，再把内部的全部换成x
        # for r in range(rows):
        #     for c in range(cols):
        #         if (board[r][c]=="O" and (r==0 or r==rows-1 or c==0 or c==cols-1)):
        #             flip(r,c)
        # for r in range(rows):
        #     for c in range(cols):
        #         if board[r][c]=="O":
        #             board[r][c]="X"
        # #复原
        # for r in range(rows):
        #     for c in range(cols):
        #         if board[r][c]=="SSS":
        #             board[r][c]="O"


        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        # rows,cols=len(board),len(board[0])
        # def capture(r,c):
        #     if (r<0 or c<0 or r==rows or c==cols or 
        #     board[r][c]!="O"):
        #         return 
        #     board[r][c]="T"
        #     capture(r-1,c)
        #     capture(r+1,c)
        #     capture(r,c+1)
        #     capture(r,c-1)
        # #change the O at the edge of the board 
        # for r in range(rows):
        #     for c in range(cols):
        #         if (board[r][c]=="O" and 
        #         (r==0 or r==rows-1 or c==0 or c==cols-1)):
        #             capture(r,c)
        # #flip the surrounded O to X
        # for r in range(rows):
        #     for c in range(cols):
        #         if board[r][c]=="O":
        #             board[r][c]="X"
        # #change back the edge T to O 
        # for r in range(rows):
        #     for c in range(cols):
        #         if board[r][c]=="T":
        #             board[r][c]="O"










        return board
17750