<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 {
    int d[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
public:
    int minDays(vector<vector<int>>& grid) {
        queue<int> q;
        int m = grid.size(), n = grid[0].size(), c = 0, s = 0;
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (grid[i][j] == 1) {
            q.push(i*n+j);
            grid[i][j] = -1;
            s++;
            while (!q.empty()) {
                int e = q.front();
                q.pop();
                for (int k = 0; k < 4; k++) {
                    int x = e/n+d[k][0], y = e%n+d[k][1];
                    if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
                        q.push(x*n+y);
                        grid[x][y] = -1;
                        s++;
                    }
                }
            }
            c++;
        }
        if (c != 1) return 0;
        if (s == 1) return 1;
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) grid[i][j] *= -1;
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (grid[i][j] == 1) {
            grid[i][j] = -1;
            int e = 1;
            for (int k = 0; k < 4; k++) {
                int x = i+d[k][0], y = j+d[k][1];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
                    q.push(x*n+y);
                    grid[x][y] = -1;
                    e++;
                    while (!q.empty()) {
                        int f = q.front();
                        q.pop();
                        for (int K = 0; K < 4; K++) {
                            int X = f/n+d[K][0], Y = f%n+d[K][1];
                            if (X >= 0 && X < m && Y >= 0 && Y < n && grid[X][Y] == 1) {
                                q.push(X*n+Y);
                                grid[X][Y] = -1;
                                e++;
                            }
                        }
                    }
                    break;
                }
            }
            if (e != s) return 1;
            for (int x = 0; x < m; x++) for (int y = 0; y < n; y++) grid[x][y] = abs(grid[x][y]); 
        }
        return 2;
    }
};
18860