<p>You are given an <code>m x n</code> binary grid <code>grid</code> where <code>1</code> represents land and <code>0</code> represents water. An <strong>island</strong> is a maximal <strong>4-directionally</strong> (horizontal or vertical) connected group of <code>1</code>&#39;s.</p>

<p>The grid is said to be <strong>connected</strong> if we have <strong>exactly one island</strong>, otherwise is said <strong>disconnected</strong>.</p>

<p>In one day, we are allowed to change <strong>any </strong>single land cell <code>(1)</code> into a water cell <code>(0)</code>.</p>

<p>Return <em>the minimum number of days to disconnect the grid</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/24/land1.jpg" style="width: 500px; height: 169px;" />
<pre>
<strong>Input:</strong> grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]

<strong>Output:</strong> 2
<strong>Explanation:</strong> We need at least 2 days to get a disconnected grid.
Change land grid[1][1] and grid[0][2] to water and get 2 disconnected island.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/24/land2.jpg" style="width: 404px; height: 85px;" />
<pre>
<strong>Input:</strong> grid = [[1,1]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> Grid of full water is also disconnected ([[1,1]] -&gt; [[0,0]]), 0 islands.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 30</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

class Solution {
public:
    int minDays(vector<vector<int>>& grid) {
        int ans=2,tot=0,m=grid.size(),n=grid[0].size(),mi=4,temp;
        bool conc=true,vis[m][n];
        for(int i=0;i<m;i++) for(int j=0;j<n;j++) {
            vis[i][j]=false;
            if(grid[i][j]) {
                tot++;
                temp=0;
                if(i && grid[i-1][j]) temp++;
                if(j && grid[i][j-1]) temp++;
                if(i<m-1 && grid[i+1][j]) temp++;
                if(j<n-1 && grid[i][j+1]) temp++; 
                mi=min(mi, temp);
            }
        }
        if(tot<2) return tot;
        queue<pair<int,int>> q; 
        for(int i=0;i<m && !q.size();i++) for(int j=0;j<n;j++) if(grid[i][j]) {q.push({i,j}); break;}
        temp=0; pair<int,int> t1,t2;
        while(q.size()) {
            t1=q.front();
            q.pop();
            if(!vis[t1.first][t1.second]) {
                vis[t1.first][t1.second] = true;
                temp++;
                int i=t1.first; int j=t1.second;
                if(i && !vis[i-1][j] && grid[i-1][j]) q.push({i-1,j});
                if(j && !vis[i][j-1]&& grid[i][j-1]) q.push({i,j-1});
                if(i<m-1 && !vis[i+1][j] && grid[i+1][j]) q.push({i+1,j});
                if(j<n-1 && !vis[i][j+1] && grid[i][j+1]) q.push({i,j+1});
            }
        }
        if(temp<tot) conc=false;
        if(!conc) ans=0;
        else if(conc && mi<ans) {
            if(tot-1-mi) ans=mi;
        }
        if(ans==2) {
            int i,j;
            for(int i1=0;i1<m && ans==2;i1++) for(int i2=0;i2<n && ans==2;i2++) {
                if(!grid[i1][i2]) continue;
                grid[i1][i2]=0;
                for(int i11=0;i11<m;i11++) for(int i22=0;i22<n;i22++) vis[i11][i22]=false;
                for(i=0;i<m && !q.size();i++) for(j=0;j<n;j++) if(grid[i][j]) {q.push({i,j}); break;}
                temp=0; pair<int,int> t1,t2;
                while(q.size()) {
                    t1=q.front();
                    q.pop();
                    i=t1.first; j=t1.second;
                    if(!vis[i][j]) {
                        vis[i][j] = true;
                        temp++;
                        if(i && !vis[i-1][j] && grid[i-1][j]) q.push({i-1,j});
                        if(j && !vis[i][j-1]&& grid[i][j-1]) q.push({i,j-1});
                        if(i<m-1 && !vis[i+1][j] && grid[i+1][j]) q.push({i+1,j});
                        if(j<n-1 && !vis[i][j+1] && grid[i][j+1]) q.push({i,j+1});
                    }
                }
                grid[i1][i2]=1;
                if(temp<tot-1) ans=1;
            }
        }
        return ans;
    }
};
32300