2658。网格中的鱼数
中的最大数量
难度：中等
>主题：数组，深度优先搜索，广度优先搜索，联合查找，矩阵
>您得到了0-索引2d矩阵网格的大小m x n，其中（r，c）表示：
如果网格[r] [c] = 0或a水含有网格[r] [c]鱼的细胞，如果网格[r] [c] > 0. 渔民可以在任何>水单元格（r，c）上启动，并且可以执行以下操作多次：>捕获细胞（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
>说明：
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.lengthn ==网格[i] .length1 >0
提示：
>从每个非零单元格运行dfs。每次您选择一个单元格时，添加您访问的细胞中包含的鱼数。解决方案：问题是要通过在网格中的任何水池开始找到fisher可以捕获的最大鱼类数量。渔民可以在当前的细胞处捕获鱼，并反复移动到任何相邻的水池（上，向下，左或右）。
要点：
网格包含土地（值0）或水（值> 0）。渔民只能移动到相邻的水池。>目的是从最佳的水单元开始找到最大的鱼类数量。 方法：
>使用
>深度优先搜索（dfs）
探索从每个水单元开始的所有可能的路径。
对于每个未访问的水单元，运行dfs来计算连接的组件中的总鱼。>
跟踪从任何连接的组件收集的最大鱼。
> 计划：>初始化一个2d访问的数组以跟踪是否探索了一个单元格。>迭代通过网格中的每个单元格。如果细胞包含水并且未访问：
从该单元格开始运行df。在连接的水池中积累了总鱼。更新到目前为止收集的最大鱼类。探索所有细胞后返回最大鱼类计数。>让我们在php中实现此解决方案： 2658。网格中的最大鱼类数量
解释：
dfs实施：对于每个水单元（r，c），如果它们是：在网格边界内部。水单元（值> 0）。在递归期间积累鱼计数。 步骤：从水单元开始，然后将其标记为访问。
递归访问其有效的邻居，总计鱼类数。返回连接的组件的总鱼类计数。
示例演练：
示例输入：
$grid = [ [0, 2, 1, 0], [4, 0, 0, 3], [1, 0, 0, 4], [0, 3, 2, 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 >在您喜欢的社交网络上分享帖子。您的支持对我来说意义重大！>
如果您想要这样的更多有用的内容，请随时关注我：
> linkedin github
以上就是网格中的最大鱼数的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1284242.html
微信扫一扫 
支付宝扫一扫 
