<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 DFS(vector<vector<char>>& board, vector<vector<int>>& vis, int r,
             int c, queue<pair<int, int>>& q) {
        int drow[] = {0, -1, 0, 1};
        int dcol[] = {-1, 0, 1, 0};
        for (int i = 0; i < 4; i++) {
            int newr = r + drow[i];
            int newc = c + dcol[i];
            if (newr >= 0 && newr < board.size() && newc >= 0 &&
                newc < board[0].size() && board[newr][newc] == 'O' &&
                vis[newr][newc] == 0) {
                vis[newr][newc] = 1;
                q.push({newr, newc});
                DFS(board, vis, newr, newc, q);
            }
        }
        return;
    }

    void solve(vector<vector<char>>& board) {
        int n = board.size();
        int m = board[0].size();
        vector<vector<int>> vis(n, vector<int>(m));
        queue<pair<int, int>> q;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                vis[i][j] = 0;
            }
        }

        int drow[] = {0, -1, 0, 1};
        int dcol[] = {-1, 0, 1, 0};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if ((i == 0 || j == 0 || i == board.size() - 1 ||
                     j == board[0].size() - 1) &&
                    (board[i][j] == 'O' && vis[i][j] == 0)) {
                    vis[i][j] = 1;
                    //q.push({i, j});
                    DFS(board, vis, i, j, q);
                    
                }
            }
        }

        while (!q.empty()) {
            q.pop();
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if ((i != 0 && j != 0 && i != board.size() - 1 &&
                     j != board[0].size() - 1) &&
                    (board[i][j] == 'O' && vis[i][j] == 0)) {
                    vis[i][j] = 1;
                    q.push({i, j});
                    DFS(board, vis, i, j, q);
                    while (!q.empty()) {
                        int row = q.front().first;
                        int col = q.front().second;
                        q.pop();
                        board[row][col] = 'X';
                    }
                }
            }
        }
    }
};

// old

//  void DFS(vector<vector<char>>& board,vector<vector<int>> &vis,int r,int
//  c,queue<pair<int,int>> &q){

//         if(r == 0 || c == 0 || r == board.size()-1 || c == board[0].size()-1
//         ){
//             if(board[r][c] == 'O'){

//                 while(!q.empty()){
//                     q.pop();

//                 }
//             }
//             else if(board[r][c] == 'X'){
//                 while(!q.empty()){
//                     int row = q.front().first;
//                     int col = q.front().second;
//                     q.pop();
//                     board[row][col] = 'X';
//                 }
//             }
//             return;
//         }
//         int drow[] = {0,-1,0,1};
//         int dcol[] = {-1,0,1,0};

//          for(int i = 0; i< 4; i++){
//              int newr = r + drow[i];
//              int newc = c + dcol[i];
//              if(newr >= 0 && newr < board.size() && newc >= 0 && newc <
//              board[0].size() && board[newr][newc] == 'O' && vis[newr][newc]
//              == 0){
//                  q.push({newr,newc});
//                  vis[newr][newc] = 1;
//                  DFS(board,vis,newr,newc,q);
//              }
//              else if( i == 3 && board[newr][newc] == 'X' && vis[newr][newc]
//              == 0){
//                  vis[newr][newc] = 1;
//                   while(!q.empty()){
//                     int row = q.front().first;
//                     int col = q.front().second;
//                     q.pop();
//                     board[row][col] = 'X';
//                 }
//              }
//          }
//          return;
//     }
//     void solve(vector<vector<char>>& board) {
//         int n = board.size();
//         int m = board[0].size();
//         vector<vector<int>> vis(n,vector<int> (m));
//         queue<pair<int,int>> q;
//         for(int i = 0; i<n ;i++){
//             for(int j = 0; j<m; j++){
//                 vis[i][j] = 0;
//             }
//         }

//         int drow[] = {0,-1,0,1};
//         int dcol[] = {-1,0,1,0};
//         for(int i = 0; i<n ;i++){
//             for(int j = 0; j<m; j++){
//                 if(i == 0 || j == 0 || i == board.size()-1 || j ==
//                 board[0].size()-1){
//                      vis[i][j] = 1;
//                      int br = i;
//                      int bc = j;
//                      q.push({i,j});
//                      for(int i = 0; i< 4; i++){
//                     int newr = i + drow[i];
//                     int newc = j + dcol[i];
//                     if(newr >= 0 && newr < board.size() && newc >= 0 && newc
//                     < board[0].size() && board[newr][newc] == 'O' &&
//                     vis[newr][newc] == 0){
//                         q.push({newr,newc});
//                         vis[newr][newc] = 1;

//                     }
//                      }
//                      DFS(board,vis,br,bc,q);
//                 }
//                 else if(board[i][j] == 'O' &&  vis[i][j] == 0){
//                      vis[i][j] = 1;
//                      q.push({i,j});
//                      DFS(board,vis,i,j,q);
//                 }
//             }
//         }
//     }
23836