网格中的最大鱼数

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中文网其他相关文章！