<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 __init__(self):
        self.r = 0
        self.c = 0
        self.d = [0, 1, 0, -1, 0]
        self.deg = [[-1] * 30 for _ in range(30)]

    def inside(self, i, j):
        return 0 <= i < self.r and 0 <= j < self.c

    def dfs0(self, i, j, grid):
        self.deg[i][j] = 0
        for a in range(4):
            s = i + self.d[a]
            t = j + self.d[a + 1]
            if self.inside(s, t) and grid[s][t] == 1:
                self.deg[i][j] += 1
                if self.deg[s][t] == -1:
                    self.dfs0(s, t, grid)

    def component(self, grid):
        cnt = 0
        for i in range(self.r):
            for j in range(self.c):
                if grid[i][j] == 1 and self.deg[i][j] == -1:
                    cnt += 1
                    self.dfs0(i, j, grid)
        return cnt

    def minDays(self, grid):
        self.r = len(grid)
        self.c = len(grid[0])

        self.deg = [[-1] * 30 for _ in range(30)]

        cnt = self.component(grid)
        if cnt != 1:
            return 0

        deg2 = []
        seen = [[False] * 30 for _ in range(30)]

        for i in range(self.r):
            for j in range(self.c):
                if 0 <= self.deg[i][j] <= 2:
                    if not seen[i][j]:
                        deg2.append((i, j))
                        seen[i][j] = True
                    for a in range(4):
                        s = i + self.d[a]
                        t = j + self.d[a + 1]
                        if self.inside(s, t) and grid[s][t] == 1 and not seen[s][t]:
                            deg2.append((s, t))
                            seen[s][t] = True

        if len(deg2) == 1:
            return 1

        for a, b in deg2:
            grid[a][b] = 0
            self.deg = [[-1] * 30 for _ in range(30)]
            cnt = self.component(grid)
            if cnt != 1:
                return 1
            grid[a][b] = 1

        return 2

243