斷開島嶼連接的最少天數

1568。斷開島嶼連接的最短天數

難度：難

主題：陣列、深度優先搜尋、廣度優先搜尋、矩陣、強連通分量

給你一個 m x n 二進位網格，其中 1 代表土地，0 代表水。 島嶼 是最大4 向（水平或垂直）連接的1 組。

如果我們剛好有一個島嶼，則稱為網格已連接，否則稱已斷開。

有一天，我們可以把任何一個陸地單元（1）變成水單元（0）。

回傳斷開電網的最小天數。

範例1：

• 輸入： grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
• 輸出： 2
• 說明：我們至少需要 2 天才能斷開電網。 將陸地網格[1][1]和網格[0][2]改為水網格並獲得2個不相連的島嶼。

範例2：

• 輸入： grid = [[1,1]]
• 輸出： 2
• 解釋：滿水網格也斷開（[[1,1]] -> [[0,0]]），0個島嶼。

約束：

• m == grid.length
• n == grid[i].length
• 1
• grid[i][j] 為 0 或 1。

提示：

1. 如果網格已經斷開，則傳回 0。
2. 如果將單一陸地更改為水域，則返回 1 斷開島嶼連接。
3. 否則回傳 2。
4. 我們最多可以在2天內斷開電網。

解：

我們需要考慮以下步驟：

解決問題的步驟：

1. 檢查初始連通性：首先，透過確定網格中是否存在多個島嶼來檢查網格是否已經斷開。如果已經斷開連接，則傳回 0。

2. 檢查單一移除是否會斷開島嶼的連接：迭代網格的每個單元格。暫時將單元格從 1 轉換為 0（如果是 1），並透過計算島嶼數量來檢查網格是否斷開。如果轉換單一儲存格會斷開島的連接，則傳回 1。

3. 兩天斷網：如果沒有單一單元轉換斷開島嶼，則可以透過轉換任兩個相鄰的陸地單元來斷開電網。因此，返回 2。

主要功能：

• DFS（深度優先搜尋） 用於尋找和計算島嶼。
• isConnected 檢查網格是否已連接。

讓我們用 PHP 實作這個解：1568。斷開島嶼連接的最短天數

<?php
// 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
?>

解釋：

• minDays() 函數處理主要邏輯。
• countIslands() 使用 DFS 計算存在的島嶼數量。
• dfs() 是探索網格並標記訪問過的陸地單元的遞歸函數。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是斷開島嶼連接的最少天數的詳細內容。更多資訊請關注PHP中文網其他相關文章！