<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 minDays(self, grid: List[List[int]]) -> int:
        #step 1. count island
        nr=len(grid)
        nc=len(grid[0])
        m=list()
        for r in range(nr):
            m.append(list(grid[r]))
        #
        ni=0
        lsize=list()
        def markisland(r,c,m):
            ret=1
            q=[(r,c)]
            m[r][c]=0
            while len(q)!=0:
                r1,c1=q.pop(0)
                for dr,dc in [(0,1),(0,-1),(1,0), (-1,0)]:
                    r2,c2=r1+dr,c1+dc
                    if r2>=0 and r2<nr and c2>=0 and c2<nc and m[r2][c2]==1:
                        q.append((r2,c2))
                        ret+=1
                        m[r2][c2]=0
                    #
            #
            return ret
        
        for r in range(nr):
            for c in range(nc):
                if m[r][c]==1:
                    ni+=1
                    isize=markisland(r,c,m)
                    lsize.append(isize)
        #
        if ni>1 or ni==0: return 0
        #print(lsize)
        #now ni==1
        if lsize[0]==2: return 2
        if lsize[0]==1 or lsize[0]==3: return 1
        #now do topo sort
        #convert to graph presentation
        #number each cell to be r*nc+c
        adj=dict()
        for r in range(nr):
            for c in range(nc):
                if grid[r][c]==0: continue
                curidx=r*nc+c
                if curidx not in adj: adj[curidx]=list()
                if r+1<nr and grid[r+1][c]==1:
                    idx2=(r+1)*nc+c
                    if idx2 not in adj: adj[idx2]=list()
                    adj[idx2].append(curidx)
                    adj[curidx].append(idx2)
                if c+1<nc and grid[r][c+1]==1:
                    idx2=r*nc+c+1
                    if idx2 not in adj: adj[idx2]=list()
                    adj[idx2].append(curidx)
                    adj[curidx].append(idx2)
        #
        deg=dict()
        for k in adj:
            deg[k]=len(adj[k])
        lstart=list()
        
        for k in deg:
            if deg[k]==1: lstart.append(k)
        #print(adj)
        #print(lstart)
        if len(lstart)>0: return 1
        #now enumerate
        #print('enumerate')
        def countisland():
            ret=0
            m=list()
            for r in range(nr):
                m.append(list(grid[r]))
            
            for r in range(nr):
                for c in range(nc):
                    if m[r][c]==1:
                        ret+=1
                        isize=markisland(r,c,m)
            #print("ret=%d"%ret)
            return ret
        for r in range(nr):
            for c in range(nc):
                if grid[r][c]==1:
                    grid[r][c]=0
                    #print('call for %d, %d'%(r,c))
                    ni=countisland()
                    if ni>1: return 1
                    grid[r][c]=1
        return 2
        
        
                    
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
                    
                    
                    
478