<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:
    
    def is_island(self, g):
        # Now, do we have exactly one island?
        unseen = {n for n in g}
        
        for n in unseen:
            break
        
        nxt = [n]
        while nxt:
            cur = nxt
            nxt = []
            for n in cur:
                if n not in unseen:
                    continue
                unseen.remove(n)
                for neighbor in g[n]:
                    nxt.append(neighbor)
        
        if unseen:
            # Multiple islands.
            return False
        return True
    
    def minDays(self, grid: List[List[int]]) -> int:
        # Each position (r, c) can be converted into a single integer (c + w * r).
        # We can build a graph of the 1s that connect to each other.
        # We can identify if there is indeed exactly one island.
        # Then, we just need to separate one node from the rest of them.
        # We can find the node with the fewest outbound edges, that's the answer.
        
        g = {}
        for r in range(len(grid)):
            for c in range(len(grid[r])):
                if grid[r][c] == 0:
                    continue
                ix = r * len(grid[r]) + c
                g[ix] = []
                for d in (-1, 1):
                    if r + d >= 0 and r + d < len(grid) and grid[r + d][c] == 1:
                        g[ix].append((r + d) * len(grid[r + d]) + c)
                    if c + d >= 0 and c + d < len(grid[r]) and grid[r][c + d] == 1:
                        g[ix].append(r * len(grid[r]) + c + d)
        
        if not g:
            return 0
        
        # We can do this in at most 2 deletions.
        # Can we do it in zero?
        if self.is_island(g):
            if len(g) < 3:
                # One island, too few elements to separate, delete them all.
                return len(g)
        else:
            # Not one island, multiple.
            return 0
        
        # What about deleting one value?
        keys = [k for k in g.keys()]
        for k in keys:
            vt = g[k]
            del g[k]
            if not self.is_island(g):
                return 1
            g[k] = vt
        
        # Then it must be two values.
        return 2
        
392