<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(object):
    def minDays(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        col_length = len(grid[0])
        row_length = len(grid)
        def get_index(row_index, col_index):
            return row_index*col_length + col_index
        def index_to_row_col(index):
            return index//col_length, index%col_length
        
        def find(clusters, target_id):
            for i, cluster in enumerate(clusters):
                if target_id in cluster:
                    return i
            return None

        def get_neighbors(row_idx, col_idx):
            result = []
            if col_idx != col_length - 1:
                result.append([row_idx, col_idx+1])
            if col_idx != 0:
                result.append([row_idx, col_idx-1])
            if row_idx != 0:
                result.append([row_idx-1, col_idx])
            if row_idx != row_length - 1:
                result.append([row_idx+1, col_idx])
            return result
        def add_list(this, that):
            for i in that:
                if i not in this:
                    this.append(i)
        
        def merge_cell(row_index, col_index, clusters):
            neighbors = [neighbor for neighbor in get_neighbors(row_index, col_index) if grid[neighbor[0]][neighbor[1]] == 1]
            my_index = get_index(row_index, col_index)
            # print('neighbors', row_index, col_index, neighbors)
            neighbors_indexes = [get_index(neighbor[0], neighbor[1]) for neighbor in neighbors]
            cluster_ids = [find(clusters, neighbor_index) for neighbor_index in neighbors_indexes + [my_index]]
            has_cluster = None
            to_delete = []
            for cluster_id in cluster_ids:
                if cluster_id is not None and has_cluster is None:
                    has_cluster = cluster_id
                    add_list(clusters[cluster_id], neighbors_indexes + [my_index])
                elif cluster_id is not None and has_cluster is not None and has_cluster != cluster_id and cluster_id not in to_delete:
                    add_list(clusters[has_cluster], clusters[cluster_id])
                    to_delete.append(cluster_id)
            for id in to_delete:
                del clusters[id]
            if has_cluster is None:
                clusters.append(neighbors_indexes + [my_index])
        
        def is_connect(row_index, col_index, partitions):
            neighbors = [neighbor for neighbor in get_neighbors(row_index, col_index) if grid[neighbor[0]][neighbor[1]] == 1]
            neighbors_indexes = [get_index(neighbor[0], neighbor[1]) for neighbor in neighbors]
            for partition in partitions:
                has_index = False
                for neighbor_index in neighbors_indexes:
                    if neighbor_index in partition:
                        has_index = True
                        partition.append(get_index(row_index, col_index))
                        break
                if not has_index:
                    return False
            return True

        
        def get_cluster_num(grid, list_merge=None, clusters=[]):
            # print(grid)
            if list_merge is None:
                for row_index, row in enumerate(grid):
                    for col_index, cell in enumerate(row):
                        if cell == 1:
                            merge_cell(row_index, col_index, clusters)
                            # print('cluster', clusters)
            else:
                for row_index, col_index in list_merge:
                    merge_cell(row_index, col_index, clusters)
                    # print('cluster', clusters)

            # print('get_cluster_result:',clusters)
            return len(clusters), clusters

        def is_splitted(row_index, col_index, clusters):
            upper_left = []
            upper_right = []
            lower_left = []
            lower_right = []
            re_merge_up = []
            re_merge_down = []
            re_merge_right = []
            re_merge_left = []
            for cluster in clusters:
                for index in cluster:
                    row, col = index_to_row_col(index)
                    if row < row_index and col < col_index:
                        upper_left.append(index)
                    elif row < row_index and col > col_index:
                        upper_right.append(index)
                    elif row > row_index and col < col_index:
                        lower_left.append(index)
                    elif row > row_index and col > col_index:
                        lower_right.append(index)
                    elif row > row_index and col == col_index:
                        re_merge_down.append([row, col])
                    elif row < row_index and col == col_index:
                        re_merge_up.append([row, col])
                    elif row == row_index and col > col_index:
                        re_merge_right.append([row, col])
                    elif row == row_index and col < col_index:
                        re_merge_left.append([row, col])
            # print('upper_left', upper_left)
            # print('upper_right', upper_right)
            # print('lower_left', lower_left)
            # print('lower_right', lower_right)
            # print('re_merge_up', re_merge_up)
            # print('re_merge_down', re_merge_down)
            # print('re_merge_right', re_merge_right)
            # print('re_merge_left', re_merge_left)
            result = []
            for partition in [upper_left, upper_right, lower_left, lower_right]:
                if len(partition) > 0:
                    result.append(partition)
            if len(result) == 1:
                return False
            length = len(result)
            
            # print(length, result)
            for connectors, partition1, partition2 in zip(
                [re_merge_up, re_merge_down, re_merge_right, re_merge_left], 
                [upper_left, lower_left, upper_right, upper_left], 
                [upper_right, lower_right, lower_right, lower_left]):
                # print('connectors', connectors, partition1, partition2)
                if len(connectors) > 0 and len(partition1) > 0 and len(partition2) > 0:
                    for row, col in connectors:
                        if is_connect(row, col, [partition1, partition2]):
                            length -= 1
                            if length == 1:
                                return False
                            else:
                                break
            if length > 1:
                return True
            return False
                    
            
        
        neighbors_island_num = [0]*col_length*row_length
        for row_index, row in enumerate(grid):
            for col_index, cell in enumerate(row):
                if cell == 1:
                    neighbors = get_neighbors(row_index, col_index)
                    my_index = get_index(row_index, col_index)
                    neighbors_island_num[my_index] = sum([grid[neighbor[0]][neighbor[1]] for neighbor in neighbors])
                        
        num_cluster, initial_clusters = get_cluster_num(grid)
        if num_cluster > 1:
            return 0
        if max(neighbors_island_num) == 1 and neighbors_island_num.count(1) == 2:
            return 2
        if 1 in neighbors_island_num:
            return 1
        two_indexes = [i for i, num in enumerate(neighbors_island_num) if num == 2]

        for index in two_indexes:
            row_index, col_index = index_to_row_col(index)
            # print('remove', row_index, col_index)
            grid[row_index][col_index] = 0
            # re_merge, partitions = partition_island(row_index, col_index, initial_clusters)
            # print(f're_merge {re_merge}\npartitions: {partitions}')
            # num, _ = get_cluster_num(grid, list_merge=re_merge, clusters=partitions)
            # if num > 1:
            if is_splitted(row_index, col_index, initial_clusters):
                return 1
            grid[row_index][col_index] = 1

        four_indexes = [i for i, num in enumerate(neighbors_island_num) if num == 4]
        for index in four_indexes:
            row_index, col_index = index_to_row_col(index)
            # print('remove', row_index, col_index)
            grid[row_index][col_index] = 0
            # re_merge, partitions = partition_island(row_index, col_index, initial_clusters)
            # print(f're_merge {re_merge}\npartitions: {partitions}')
            # num, _ = get_cluster_num(grid, list_merge=re_merge, clusters=partitions)
            # if num > 1:
            #     return 1
            if is_splitted(row_index, col_index, initial_clusters):
                return 1
            grid[row_index][col_index] = 1

        if 2 in neighbors_island_num:
            return 2

        if num_cluster == 1:
            return 1

        return 0
307