網格中的最大魚數

2658。網格中的魚數

中的最大數量

難度：中等

>主題：數組，深度優先搜索，廣度優先搜索，聯合查找，矩陣

>您得到了0-索引2D矩陣網格的大小m x n，其中（r，c）表示：

如果網格[r] [c] = 0或

a
• 水含有網格[r] [c]魚的細胞，如果網格[r] [c]＆gt; 0.
• 漁民可以在任何>水單元格（r，c）上啟動，並且可以執行以下操作多次：

>捕獲細胞（R，C）或的所有魚 移動到任何相鄰的水

單元格。

>
返回
• 最大魚類數量，如果Fisher最佳選擇他的起始細胞，則可以捕獲，或者如果不存在水單元，則可以捕獲0。 An 相鄰單元格（r，c）的細胞是一個單元格（r，c 1），（r，c -1），（r 1，c）或（r）或（r -1，c）如果存在。
>

>

>示例1：

輸入： grid = [[[0,2,1,0]，[4,0,0,3]，[1,0,0,4]，[0,3,2,0 ] ]

>輸出：7

>說明：

Fisher可以從細胞（1,3）開始並收集3條魚，然後移動到細胞（2,3）並收集4條魚。

• >>示例2：
• >輸入： grid = [[[1,0,0,0]，[0,0,0,0]，[0,0,0,0]，[0,0,0, 1] ]

>輸出：

1

>說明：

Fisher可以從細胞（0,0）或（3,3）開始並收集一條魚。

>約束：
• >
m == grid.length
• n ==網格[i] .length
1＆lt; = m，n＆lt; = 10
• > 0＆lt; = grid [i] [j]＆lt; = 10 >

提示：

>從每個非零單元格運行dfs。

• 每次您選擇一個單元格時，添加您訪問的細胞中包含的魚數。
• 解決方案：
問題是要通過在網格中的任何水池開始找到Fisher可以捕獲的最大魚類數量。漁民可以在當前的細胞處捕獲魚，並反复移動到任何相鄰的水池（上，向下，左或右）。

要點：

1. 網格包含土地（值0）或水（值＆gt; 0）。
漁民只能移動到相鄰的水池。
2. >
目的是從最佳的水單元開始找到最大的魚類數量。
方法：

>使用

>深度優先搜索（DFS）
1. 探索從每個水單元開始的所有可能的路徑。 對於每個未訪問的水單元，運行DFS來計算連接的組件中的總魚。 > 跟踪從任何連接的組件收集的最大魚。
>
計劃：

>初始化一個2D訪問的數組以跟踪是否探索了一個單元格。 >

迭代通過網格中的每個單元格。

如果細胞包含水並且未訪問：
從該單元格開始運行DF。
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
?>

>水單元（value＆gt; 0）。

在遞歸期間積累魚計數。

• 步驟：
  • 從水單元開始，然後將其標記為訪問。
  • 遞歸訪問其有效的鄰居，總計魚類數。
  返回連接的組件的總魚類計數。
• 示例演練：

示例輸入：

執行：
2. >從（1，3）開始（值= 3）。運行DFS：
3. （1，3）→（2，3）（值= 4）。
>

總釣魚= 3 4 =7。 >

探索其他水池，但沒有連接的組分的總魚類數量較高。

>輸出：7。

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

時間複雜性：

1. • dfs遍歷：
   一次訪問每個單元→o（m×n）。
   >總體複雜性：
   o（m×n），其中m和n是網格尺寸。
2. 輸出以示例：

>示例1：

7

• >示例2： 1
• >該解決方案有效地使用DFS探索水池的連接組件，並通過從任何水池開始捕獲的漁民可捕獲的最大魚類。這種方法可確保最佳的探索，並且可以很好地適合給定的約束。 >
聯繫鏈接

如果您發現此系列有幫助，請考慮在Github上給出 reposority >在您喜歡的社交網絡上分享帖子？您的支持對我來說意義重大！ >

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

>

• LinkedIn
• github

以上是網格中的最大魚數的詳細內容。更多資訊請關注PHP中文網其他相關文章！