<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:



    void go(vector<vector<int>>& visit, int & change, int x, int y, vector<vector<int>> & grid) {
        if(x < 0 || y < 0 || x == visit.size() || y == visit[0].size() || visit[x][y]==1 || grid[x][y]==0) {
            return;
        }
        int cnt = 0;
        visit[x][y]=1;
        if(x-1 >= 0) {
            if(grid[x-1][y]) {
                cnt++;
            }
        }
        if(x+1<visit.size()) {
            if(grid[x+1][y]) {
                cnt++;
            }
        }
        if(y-1 >= 0) {
            if(grid[x][y-1]) {
                cnt++;
            }
        }
        if(y+1 < visit[0].size()) {
            if(grid[x][y+1]) {
                cnt++;
            }
        }
        change = min(change, cnt);
        go(visit, change, x-1, y, grid);
        go(visit, change, x+1, y, grid);
        go(visit, change, x, y-1, grid);
        go(visit, change, x, y+1, grid);
        return;
    }
    void go_(vector<vector<int>>& visit, vector<vector<int>>& grid, int x, int y) {
        if(x < 0 || y < 0 || x == visit.size() || y == visit[0].size() || visit[x][y]==1 || grid[x][y]==0) {
            return;
        }
        visit[x][y]=1;
        go_(visit, grid, x-1, y);
        go_(visit, grid, x+1, y);
        go_(visit, grid, x, y-1);
        go_(visit, grid, x, y+1);
        return;
    }
    int minDays(vector<vector<int>>& grid) {
        int island_cnt=0, m = grid.size(), n = grid[0].size(), ans = INT_MAX, total=0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j]) {
                    total++;
                }
            }
        }
        vector<vector<int>> visit(m,vector<int>(n,0));
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] && visit[i][j]==0) {
                    island_cnt++;
                    if(island_cnt==2) {
                        return 0;
                    }
                    int change = INT_MAX;
                    go(visit,change,i,j,grid);
                    ans=min(ans,change);
                }       
            }
        } 
        if(island_cnt==0) {
            return 0;
        }
        if(ans>1) {
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    if(grid[i][j]) {
                        grid[i][j]=0;
                        vector<vector<int>> v(m, vector<int>(n,0));
                        int is=0;
                        for(int k = 0; k < m; k++) {
                            for(int l = 0; l < n; l++) {
                                if(grid[k][l]&&v[k][l]==0) {
                                    is++;
                                    if(is==2) {
                                        return 1;
                                    }
                                    go_(v, grid, k, l);
                                }
                            }
                        }
                        grid[i][j]=1;
                    }
                }
            }
            
        }
        total-=ans;
        if(total==1) {
            ans++;
        }
        return ans;
    }
};
21660