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可以捕獲的最大魚類數量。漁民可以在當前的細胞處捕獲魚，並反复移動到任何相鄰的水池（上，向下，左或右）。
要點：
- 網格包含土地（值0）或水（值＆gt; 0）。
漁民只能移動到相鄰的水池。 - >
目的是從最佳的水單元開始找到最大的魚類數量。
-
方法：
>使用>深度優先搜索（DFS）- 探索從每個水單元開始的所有可能的路徑。
對於每個未訪問的水單元，運行DFS來計算連接的組件中的總魚。 >
跟踪從任何連接的組件收集的最大魚。
>
-
計劃：
-
>初始化一個2D訪問的數組以跟踪是否探索了一個單元格。 >
迭代通過網格中的每個單元格。
如果細胞包含水並且未訪問：
-
從該單元格開始運行DF。
- 在連接的水池中積累了總魚。
更新到目前為止收集的最大魚類。 -
-
探索所有細胞後返回最大魚類計數。 -
- >讓我們在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
?>
登入後複製
在遞歸期間積累魚計數。
-
步驟：
-
- 從水單元開始，然後將其標記為訪問。
- 遞歸訪問其有效的鄰居，總計魚類數。
返回連接的組件的總魚類計數。
-
示例演練：
示例輸入：
執行：
-
- >從（1，3）開始（值= 3）。運行DFS：
-
（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]
];
登入後複製
時間複雜性：
-
- dfs遍歷：
一次訪問每個單元→o（m×n）。
-
>總體複雜性：
o（m×n），其中m和n是網格尺寸。
-
輸出以示例：
-
>示例1： 7
- >示例2： 1
- >該解決方案有效地使用DFS探索水池的連接組件，並通過從任何水池開始捕獲的漁民可捕獲的最大魚類。這種方法可確保最佳的探索，並且可以很好地適合給定的約束。 >
聯繫鏈接
如果您發現此系列有幫助，請考慮在Github上給出 reposority >在您喜歡的社交網絡上分享帖子？您的支持對我來說意義重大！ >
如果您想要這樣的更多有用的內容，請隨時關注我：>
以上是網格中的最大魚數的詳細內容。更多資訊請關注PHP中文網其他相關文章！
