斷開島嶼連接的最少天數

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

以上就是斷開島嶼連接的最少天數的詳細內容，更多請關注愛掏網 - it200.com其它相關文章！