グリッド内の魚の最大数

2658。グリッド内の魚の最大数

難易度： medium

トピック：配列、深さ第一検索、幅広い最初の検索、ユニオンファインド、マトリックス

0インデックス 2Dマトリックスグリッドがサイズm x nの2Dマトリックスグリッドを与えられます。ここで（r、c）

グリッド[r] [c] = 0、または

グリッド[r] [c]魚を含む
• a 水細胞、グリッドの場合[r] [c]＆gt; 0.
• 漁師は任意の水
セル（r、c）から始まり、次の操作をいつでも実行できます。

細胞ですべての魚を捕まえます（r、c）、または 任意の隣接する

水

セルに移動します。
• return最大
魚の数は、最初の細胞を最適に選択した場合にキャッチできる魚、または水セルが存在しない場合は0

an

隣接する細胞の細胞（r、c）は、細胞の1つ（r、c 1）、（r、c -1）、（r 1、c）または（rの1つです。 -1、c）存在する場合 例1：

input：grid = [[0,2,1,0]、[4,0,0,3]、[1,0,0,4]、[0,3,2,0] ]

output：7

• 説明：フィッシャーは細胞（1,3）から始まり、3匹の魚を集めてから、細胞（2,3）に移動して4匹の魚を集めることができます。
• 例2：

input：

grid = [[1,0,0,0]、[0,0,0,0]、[0,0,0,0]、[0,0,0,1] ]

output：

1

説明：
• フィッシャーは、細胞（0,0）または（3,3）で始まり、単一の魚を集めることができます。
制約：
m == grid.length
• n == grid [i] .length
1＆lt; = m、n＆lt; = 10

0＆lt; = grid [i] [j]＆lt; = 10

ヒント：
各ゼロセルからdfsを実行します。
セルを選ぶたびに開始するたびに、訪問する細胞に含まれる魚の数を加算します。

解決策：

問題は、漁師がグリッド内の任意の水セルから始めて捕まえることができる魚の最大数を見つけることです。漁師は、現在の細胞で魚を捕まえて、隣接する水セル（上、下、左、または右）に繰り返し移動できます。

キーポイント：

1. グリッドには、土地（値0）または水（値＆gt; 0）のいずれかのセルが含まれています。
漁師は隣接する水セルにのみ移動できます。
目的は、可能な限り最高の水セルから始まる魚の最大数を見つけることです。
アプローチ：

深度検索（DFS）
1. を使用して、各水セルから始まる可能性のあるすべてのパスを探索します。 訪問されていない水セルごとに、DFSを実行して、接続されたコンポーネントの総魚を計算します。 接続されたコンポーネントから収集された最大魚を追跡します
2. プラン：
2Dにアクセスした配列を初期化して、セルが調査されたかどうかを追跡します。 グリッド内の各セルを反復します。

細胞に水が含まれていて訪問されていない場合：

そのセルから始まるDFSを実行します
1. 接続された水セルに総魚が蓄積します。
2. これまでに収集された最大魚を更新します
3. すべての細胞を探索した後、最大魚の数を返します
   このソリューションをPHP：
   • 2658に実装しましょう。グリッド内の魚の最大数
説明：
DFS実装：

各水セル（R、c）については、隣人が次の場合に再帰的に探索します。 グリッド境界内の

<?php /**
 * @param Integer[][] $grid
 * @return Integer
 */
function findMaxFish($grid) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function for DFS
 * @param $r
 * @param $c
 * @param $grid
 * @param $visited
 * @param $rows
 * @param $cols
 * @param $directions
 * @return array|bool|int|int[]|mixed|null
 */
function dfs($r, $c, &$grid, &$visited, $rows, $cols, $directions) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]];
echo getMaxFish($grid); // Output: 7

// Example 2
$grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]];
echo getMaxFish($grid); // Output: 1
?>

visited。

水セル（値＆gt; 0）。

• 再帰中に魚の数を蓄積します。
  ステップ：
  • 水セルから始めて、訪問どおりにマークします。
  有効な隣人を再帰的に訪問し、魚の数を合計します。
• 接続されたコンポーネントの合計魚の数を返します。

例のウォークスルー：

入力の例：
2. 実行：
（1、3）（値= 3）で開始します。 DFSを実行する：

（1、3）→（2、3）（値= 4）。

合計魚= 3 4 =7。

$grid = [
    [0, 2, 1, 0],
    [4, 0, 0, 3],
    [1, 0, 0, 4],
    [0, 3, 2, 0]
];

他の水セルを探索しますが、接続されたコンポーネントは魚カウントが高くなることはありません。

出力：7。
1. • 時間の複雑さ：
   dfsトラバーサル：
各セルが一度訪問されます→o（m×n）。
2. 全体的な複雑さ：
o（m×n）、ここで、mとnはグリッド寸法です。
例のための出力：

例1：
• 7
例2：
• 1
溶液は、DFSを効率的に使用して、水セルの接続された成分を探索し、水セルから始まる漁師がキャッチ可能な最大魚を計算します。このアプローチは、最適な調査を保証し、与えられた制約に合わせてうまく機能します。

連絡先リンク

このシリーズが役立つと思った場合は、

リポジトリをGitHubにスターに提供するか、お気に入りのソーシャルネットワークで投稿を共有してください。あなたのサポートは私にとって大きな意味があります！

このようなもっと役立つコンテンツが必要な場合は、お気軽にフォローしてください：
• linkedIn
• github

以上がグリッド内の魚の最大数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。