LeetCode 题解工作台
网格图中鱼的最大数目
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，其中下标在 (r, c) 处的整数表示： 如果 grid[r][c] = 0 ，那么它是一块 陆地 。 如果 grid[r][c] > 0 ，那么它是一块 水域 ，且包含 grid[r][c] 条鱼。 一位渔夫可以从任意 水域 …
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
根据题目描述，我们只需要找出每块连通的水域中鱼的数目，然后取最大值即可。因此，我们可以使用深度优先搜索的方法来解决本题。 我们定义一个函数 $dfs(i, j)$，表示从网格图中的第 行第 列的格子出发，可以捕捞到的最大鱼数。函数 $dfs(i, j)$ 的执行逻辑如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，其中下标在 (r, c) 处的整数表示：
- 如果
grid[r][c] = 0，那么它是一块 陆地 。 - 如果
grid[r][c] > 0，那么它是一块 水域 ，且包含grid[r][c]条鱼。
一位渔夫可以从任意 水域 格子 (r, c) 出发，然后执行以下操作任意次：
- 捕捞格子
(r, c)处所有的鱼，或者 - 移动到相邻的 水域 格子。
请你返回渔夫最优策略下， 最多 可以捕捞多少条鱼。如果没有水域格子，请你返回 0 。
格子 (r, c) 相邻 的格子为 (r, c + 1) ，(r, c - 1) ，(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 解释：渔夫可以从格子(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 解释：渔夫可以从格子 (0,0) 或者 (3,3) ，捕捞 1 条鱼。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 100 <= grid[i][j] <= 10
解题思路
方法一：DFS
根据题目描述，我们只需要找出每块连通的水域中鱼的数目，然后取最大值即可。因此，我们可以使用深度优先搜索的方法来解决本题。
我们定义一个函数 ，表示从网格图中的第 行第 列的格子出发，可以捕捞到的最大鱼数。函数 的执行逻辑如下：
我们用一个变量 来记录当前格子中的鱼的数目，然后将当前格子中的鱼的数目置为 ，表示已经捕捞过了。然后我们遍历当前格子的上下左右四个方向，如果某个方向的格子 在网格图内且是水域格子，那么我们就递归调用 函数，将返回值加到 中。最后返回 即可。
在主函数中，我们遍历所有的格子 ，如果当前格子是水域格子，那么我们就调用 函数，取返回值的最大值作为答案返回即可。
时间复杂度 ，空间复杂度 。其中 和 分别是网格图的行数和列数。
class Solution:
def findMaxFish(self, grid: List[List[int]]) -> int:
def dfs(i: int, j: int) -> int:
cnt = grid[i][j]
grid[i][j] = 0
for a, b in pairwise((-1, 0, 1, 0, -1)):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and grid[x][y]:
cnt += dfs(x, y)
return cnt
m, n = len(grid), len(grid[0])
ans = 0
for i in range(m):
for j in range(n):
if grid[i][j]:
ans = max(ans, dfs(i, j))
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O((n \cdot m) \cdot \alpha(n \cdot m)) |
| 空间 | O(n \cdot m) |
面试官常问的追问
外企场景- question_mark
Ability to handle DFS-based grid problems.
- question_mark
Experience with depth-first search traversal techniques.
- question_mark
Awareness of common pitfalls when traversing connected components.
常见陷阱
外企场景- error
Forgetting to mark cells as visited, leading to redundant calculations.
- error
Not handling grid boundaries correctly during DFS traversal.
- error
Misinterpreting the problem as a simple grid search without considering the connected components.
进阶变体
外企场景- arrow_right_alt
Implementing BFS instead of DFS for grid traversal.
- arrow_right_alt
Introducing different grid sizes and ensuring efficient traversal.
- arrow_right_alt
Handling larger grids with optimized algorithms for performance.