島を切断するまでの最小日数

1568年。島の接続を解除するための最小日数

難易度: 難しい

トピック: 配列、深さ優先検索、幅優先検索、行列、強結合成分

m x n のバイナリ グリッドが与えられます。1 は土地を表し、0 は水を表します。 島は、最大4方向 (水平または垂直) に接続された 1 のグループです。

正確に 1 つの島がある場合、グリッドは接続されていると言われ、それ以外の場合は切断されていると言われます。

1 日で、**** 任意の単一の陸地セル (1) を水のセル (0) に変更することができます。

グリッドを切断する最小日数を返します。

例 1:

• 入力: グリッド = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
• 出力: 2
• 説明: 切断されたグリッドを取得するには少なくとも 2 日かかります。 土地のグリッド[1][1]とグリッド[0][2]を水に変更し、切断された島を 2 つ取得します。

例 2:

• 入力: グリッド = [[1,1]]
• 出力: 2
• 説明: 満水のグリッドも切断され ([[1,1]] -> [[0,0]])、島は 0 つあります。

制約:

• m == グリッドの長さ
• n == グリッド[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 日間の切断: 単一のセル変換によってアイランドが切断されない場合は、任意の 2 つの隣接する陸上セルを変換することでグリッドを切断できます。したがって、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 で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が島を切断するまでの最小日数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。