2658。网格中的鱼数
中的最大数量难度：中等
>主题：数组，深度优先搜索，广度优先搜索，联合查找，矩阵
>您得到了0-索引2d矩阵网格的大小m x n，其中（r，c）表示：
- a
- 水含有网格[r] [c]鱼的细胞，如果网格[r] [c] > 0.
- >水单元格（r，c）上启动，并且可以执行以下操作多次：
移动到任何相邻的水单元格。
>- 返回
- 最大鱼类数量，如果fisher最佳选择他的起始细胞，则可以捕获，或者如果不存在水单元，则可以捕获0。
and
相邻的 单元格（r，c）是一个单元格（r，c 1），（r，c -1），（r 1，c）或（r 1，c）或（r -1，c）如果存在。 >
>示例1：
输入： grid = [[[0,2,1,0]，[4,0,0,3]，[1,0,0,4]，[0,3,2,0] ]
>输出：7
>说明：
- >>示例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 < = m，n < = 10
- > 0 < = grid [i] [j] < = 10
提示：
- >从每个非零单元格运行dfs。
- 每次您选择一个单元格时，添加您访问的细胞中包含的鱼数。
- 解决方案：
要点：
网格包含土地（值0）或水（值> 0）。- 渔民只能移动到相邻的水池。 >
- 目的是从最佳的水单元开始找到最大的鱼类数量。
>使用
>深度优先搜索（dfs）探索从每个水单元开始的所有可能的路径。
对于每个未访问的水单元，运行dfs来计算连接的组件中的总鱼。跟踪从任何连接的组件收集的最大鱼。
>- 计划：
- >初始化一个2d访问的数组以跟踪是否探索了一个单元格。
- 迭代通过网格中的每个单元格。
从该单元格开始运行df。
- 在连接的水池中积累了总鱼。
- 更新到目前为止收集的最大鱼类。
- 探索所有细胞后返回最大鱼类计数。
- >让我们在php中实现此解决方案：
<?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
?>
解释：
-
dfs实施：
- 对于每个水单元（r，c），如果它们是：
- 在网格边界内部。
-
- 水单元（值> 0）。
- 在递归期间积累鱼计数。
- 水单元（值> 0）。
- 从水单元开始，然后将其标记为访问。
递归访问其有效的邻居，总计鱼类数。
返回连接的组件的总鱼类计数。
示例输入：
$grid = [
[0, 2, 1, 0],
[4, 0, 0, 3],
[1, 0, 0, 4],
[0, 3, 2, 0]
];
执行：
-
- >从（1，3）开始（值= 3）。运行dfs：
- （1，3）→（2，3）（值= 4）。
- > 总钓鱼= 3 4 =7。
> >输出：7。
- dfs遍历： 一次访问每个单元→o（m×n）。
- >总体复杂性：
- o（m×n），其中m和n是网格尺寸。
>示例1：
7
- >示例2：
- 1
- >该解决方案有效地使用dfs探索水池的连接组件，并通过从任何水池开始捕获的渔民可捕获的最大鱼类。这种方法可确保最佳的探索，并且可以很好地适应给定的约束。 >
联系链接 - 如果您发现此系列有帮助，请考虑在github上给出
reposority cository >在您喜欢的社交网络上分享帖子。您的支持对我来说意义重大！
如果您想要这样的更多有用的内容，请随时关注我：
>- github
