<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 {
public:
    void solve(vector<vector<char>>& board) {
        int m=board.size(), n=board[0].size();
        int start=0, end=n-1;
        // for(int i=1; i<m-1; i++){
        //     start=0, end=n-1;
        //     while(board[i][start]!='X' && start<end) start++;
        //     while(board[i][start]=='X' && start<end) start++;
        //     while(board[i][end]!='X' && end>start) end--;
        //     while(board[i][end]=='X' && end>start) end--;
        //     //cout<<i<<" "<<start<<" "<<end<<endl;
        //     if(start>0 && end<n-1){
        //         for(int j=start; j<=end; j++){
        //             if(board[i][j]=='O') board[i][j]='2';
        //         }
        //     } 
        // }
        // for(int j=1; j<n-1; j++){
        //     start=0, end=m-1;
        //     while(board[start][j]!='X' && start<end) start++;
        //     while(board[start][j]=='X' && start<end) start++;
        //     while(board[end][j]!='X' && end>start) end--;
        //     while(board[end][j]=='X' && end>start) end--;
        //     //cout<<j<<" "<<start<<" "<<end<<endl;
        //     if(start>0 && end<m-1){
        //         for(int i=start; i<=end; i++){
        //             if(board[i][j]=='2') board[i][j]='4';
        //         }
        //     } 
        // }
        // for(int i=0; i<m ; i++){
        //     for(int j=0; j<n; j++){
        //         cout<<board[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        for(int i=1; i<m-1 ; i++){
            for(int j=1; j<n-1; j++){
                if(board[i][j]!='X' && board[i][j]!='Y'){
                    //cout<<i<<" "<<j<<" "<<board[i][j]<<endl;
                    if(isRegionValid(board, i, j)){
                        cout<<"Filling region with X"<<endl;
                        fillRegion(board, i, j, 'X');
                    }else{
                        cout<<"Filling region with Y"<<endl;
                        for(int i=0; i<m ; i++){
                            for(int j=0; j<n; j++){
                                if(board[i][j]=='Y') board[i][j]='O';
                                //cout<<board[i][j]<<" ";
                            }
                            //cout<<endl;
                        }
                        fillRegion(board, i, j, 'Y');
                    }
                }
            }
            //cout<<endl;
        }
        for(int i=0; i<m ; i++){
            for(int j=0; j<n; j++){
                if(board[i][j]=='Y') board[i][j]='O';
                //cout<<board[i][j]<<" ";
            }
            //cout<<endl;
        }
    }

    bool isRegionValid(vector<vector<char>>& board, int i, int j) {
        if(i<0 || j<0 || i>=board.size() || j>=board[0].size()) return false;
        //cout<<i<<" "<<j<<" "<<board[i][j]<<endl;
        if(board[i][j]=='Y' || board[i][j]=='X') return true;
        if(board[i][j]=='O') board[i][j]='Y';
        return isRegionValid(board, i+1, j) && isRegionValid(board, i, j+1) && isRegionValid(board, i, j-1) && isRegionValid(board, i-1, j);
    }

    void fillRegion(vector<vector<char>>& board, int i, int j, char t) {
        if(i<0 || j<0 || i>=board.size() || j>=board[0].size()) return;
        //cout<<i<<" "<<j<<" "<<board[i][j]<<endl;
        if(board[i][j]=='X' || board[i][j]==t) return;
        board[i][j]=t;
        fillRegion(board, i-1, j, t);
        fillRegion(board, i+1, j, t);
        fillRegion(board, i, j+1, t);
        fillRegion(board, i, j-1, t);
        return;
    }
};
18316