1568. Minimum Number of Days to Disconnect Island

[mah-shamim]

Topics: Array, Depth-First Search, Breadth-First Search, Matrix, Strongly Connected Component

You are given an m x n binary grid grid where 1 represents land and 0 represents water. An island is a maximal 4-directionally (horizontal or vertical) connected group of 1's.

The grid is said to be connected if we have exactly one island, otherwise is said disconnected.

In one day, we are allowed to change a****ny single land cell (1) into a water cell (0).

Return the minimum number of days to disconnect the grid.

Example 1:

• Input: grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
• Output: 2
• Explanation: 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.

Example 2:

• Input: grid = [[1,1]]
• Output: 2
• Explanation: Grid of full water is also disconnected ([[1,1]] -> [[0,0]]), 0 islands.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 30
• grid[i][j] is either 0 or 1.

Hint:

1. Return 0 if the grid is already disconnected.
2. Return 1 if changing a single land to water disconnect the island.
3. Otherwise return 2.
4. We can disconnect the grid within at most 2 days.

[mah-shamim]

We need to consider the following steps:

Steps to Solve the Problem:

1. Check Initial Connectivity: First, check if the grid is already disconnected by determining if there is more than one island in the grid. If it's already disconnected, return 0.

2. Check If Single Removal Disconnects the Island: Iterate through each cell of the grid. Temporarily convert the cell from 1 to 0 (if it's 1) and check if the grid becomes disconnected by counting the number of islands. If converting a single cell disconnects the island, return 1.

3. Two Day Disconnection: If no single cell conversion disconnects the island, then the grid can be disconnected by converting any two adjacent land cells. Therefore, return 2.

Key Functions:

• DFS (Depth-First Search) to find and count islands.
• isConnected to check if the grid is connected.

Let's implement this solution in PHP: 1568. Minimum Number of Days to Disconnect Island

<?php
function minDays($grid) {
    $m = count($grid);
    $n = count($grid[0]);

    // Check if the grid is already disconnected
    if (countIslands($grid) != 1) {
        return 0;
    }

    // Check if a single land removal disconnects the grid
    for ($i = 0; $i < $m; $i++) {
        for ($j = 0; $j < $n; $j++) {
            if ($grid[$i][$j] == 1) {
                $grid[$i][$j] = 0; // Temporarily convert to water
                if (countIslands($grid) != 1) {
                    return 1;
                }
                $grid[$i][$j] = 1; // Revert back to land
            }
        }
    }

    // Otherwise, it will take 2 days to disconnect the grid
    return 2;
}

function countIslands(&$grid) {
    $m = count($grid);
    $n = count($grid[0]);
    $visited = array_fill(0, $m, array_fill(0, $n, false));
    $islandCount = 0;

    for ($i = 0; $i < $m; $i++) {
        for ($j = 0; $j < $n; $j++) {
            if ($grid[$i][$j] == 1 && !$visited[$i][$j]) {
                $islandCount++;
                dfs($grid, $i, $j, $visited);
            }
        }
    }

    return $islandCount;
}

function dfs(&$grid, $i, $j, &$visited) {
    $m = count($grid);
    $n = count($grid[0]);
    $directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];

    $visited[$i][$j] = true;

    foreach ($directions as $dir) {
        $ni = $i + $dir[0];
        $nj = $j + $dir[1];

        if ($ni >= 0 && $nj >= 0 && $ni < $m && $nj < $n && $grid[$ni][$nj] == 1 && !$visited[$ni][$nj]) {
            dfs($grid, $ni, $nj, $visited);
        }
    }
}

// Example usage:
$grid1 = [
    [0, 1, 1, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0]
];
echo minDays($grid1); // Output: 2

$grid2 = [
    [1, 1]
];
echo minDays($grid2); // Output: 2
?>

Explanation:

• minDays() function handles the main logic.
• countIslands() counts how many islands are present using DFS.
• dfs() is the recursive function to explore the grid and mark visited land cells.

[basharul-siddike]

Thanks for solving the problem of "Minimum Number of Days to Disconnect Island"

[mah-shamim]

Thanks