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

'''
not guaranteed to be disconnected to begin with
so do we need a check to see how many islands first? 
no way right... 
but once we find the size of the only island
there isnt a clear cut way of decreasing systematically? 

given a single island
could we just find the nodes with the minimum number of connections? 
no that doesnt work for a block 
how about max? no 
it seems like its related to if a block is adjacent to few connection blocks
we cant even say its if a block has n number of connections etc 
like a full block, you will always have a second shortest diagonal 
that you can remove 
the corners are the smallest connections, but you cant remove them cause then you just
form a new border
so yu need to be nested
hmm could it be the larggest connected block adjacent to the smallest? 
like if I have a block
then I just add one block, the block to remove is now the block adjacent to the new block
it used to be the second shortest diag 
its hard to prove this
im thinkign if you choose the fewest connection block, then find its largest 
connection adjacent, thats a point connecting with the "larger" body

you still need to check every removal if its a new island though ....
its 600 for an mn sweep
360000 - 3.6 * 10^4 for an m^2n^2 sweep
i guesss you could go brute force but no way this is a hard
no you cant go brute force cause then you're going down a backtracking approach
that could be (mn)^mn

you do have to break ties though you could have multiple min connections then 
different adjacent maxes 
conversely find the largest with the min -> but its not necessarily the max
no i dont think it works wait maybe it does
'''
'''
nope doesnt work
heres the fucking hint:
Return 0 if the grid is already disconnected.
Return 1 if changing a single land to water disconnect the island.
Otherwise return 2.
We can disconnect the grid within at most 2 days.

im just going to count connected cells
if removing each does not reduce by gteq 2 then its still connected
my implementation is bit messy because I'm using counts and starting from the original island cells
instead of from the beginning of the grid

the proof is not really there
its kind of like consider the left most and top most
then we have at most two connections
the idea being that its 4 connected, so removing 2 connections is always sufficient
by definition of an island
we have some "edge" cases not really edge but where removing neighbors isnt sufficient
need to remove self:
[[1, 1]
 [1, 0]]
 need to remove 0, 0 for example in one (one articulation point)
or [[1,1]]
'''
#(mn)^2 test flip each cell 
class Solution:
    def minDays(self, grid: List[List[int]]) -> int:
        def count_connected(row, col, seen):
            queue = collections.deque([(row, col)])
            connections = []
            while queue:
                for _ in range(len(queue)):
                    row, col = queue.popleft()
                    connections.append((row, col))
                    neighbors = [(row + 1, col), (row - 1, col), (row, col + 1), (row, col - 1)]
                    for next_row, next_col in neighbors:
                        if not (0 <= next_row < len(grid) and 0 <= next_col < len(grid[0])):
                            continue
                        if grid[next_row][next_col] == 0: continue
                        if (next_row, next_col) in seen: continue
                        seen.add((next_row, next_col))
                        queue.append((next_row, next_col))
            return connections

        #count number islands initiallly
        #and get connections
        number_islands = 0
        seen = set()
        island_row, island_col = 0, 0
        island_cells = []
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 0: continue
                if (i, j) in seen: continue
                number_islands += 1
                if number_islands == 2: return 0
                island_row, island_col = i, j
                seen.add((i, j))
                island_cells = count_connected(i, j, seen)

        if number_islands != 1: return 0

        #for each island cell consider removing it and check if we have gteq 2 decrease
        number_cells = len(island_cells)
        if number_cells == 1: return 1 #edge case only one cell, no neighbors
        for row, col in island_cells:
            grid[row][col] = 0
            #we need to test on a neighbor entry, not this cell 
            neighbors = [(row + 1, col), (row - 1, col), (row, col + 1), (row, col - 1)]
            for next_row, next_col in neighbors:
                if not (0 <= next_row < len(grid) and 0 <= next_col < len(grid[0])):
                    continue
                if grid[next_row][next_col] == 0: continue

                new_connected_cells = count_connected(next_row, next_col, set([(next_row, next_col)]))

                if len(new_connected_cells) == number_cells - 1: break #still connected
                elif len(new_connected_cells) < number_cells - 1: return 1 #disconnected with 1
            grid[row][col] = 1

        return 2 #we cannot disconnect in 1 or 0 moves
        
1205