题目描述
思路解析动画文字版
记牢这一句:片内求和,片间取最大。同一片相连水域的鱼要全部加起来,不同片之间则是挑总和最大的那一片。下面从左上角开始,一片一片地捞。
工作网格 · 水域格写鱼数,陆地写点：这是工作网格。写着数字的是水域格,数字就是鱼数;写着点的是陆地格,值为 0,渔夫过不去。一眼看去,数字被点分隔成了四小簇:左上两格、左中两格、右中两格、下方两格。接下来就把这四片逐一走一遍,每走完一片记下它的鱼总数,再挑出最大的那一片。
外层扫描 · 发现第一片水域,起点 (0,1)：外层循环从左上角开始逐格扫。跳过所有陆地,第一个碰到的水域是 (0,1),里面有 2 条鱼。以它为起点发起一次 DFS,先把这 2 条记进本片渔获,再顺着相连水域往外扩。
从 (0,1) 看四邻 · 右边是水域：站在起点 (0,1),按上右下左的顺序看四个邻居。别的方向要么出界、要么是陆地 0,只有右边的 (0,2) 是相连的水域、还没捞过。DFS 的规矩就是先钻进这条路走到底,所以下一步游到 (0,2)。
游到 (0,2) · 再捞 1 条：顺着相连水域游到 (0,2),把这里的 1 条也捞走,当前格立刻置 0 当访问标记,免得回头重捞。本片渔获累加到 3 条。它四周再没有新的相连水域了,这一片就到此为止。
第一片走完 · 本片总渔获 = 3：这一片相连水域走完了,一共 2 个格子,鱼数加起来是 3 条。这就是渔夫从这片里出发能捞到的全部。接下来把它和目前记下的最优渔获比一比。
第一片结算 · 刷新最优：这是扫到的第一片水域,一共 3 条,还没有别的片能比。它直接成为当前最优,把这一片标成绿色表示它是眼下最肥的一片,当前最优渔获记成 3 条。接着往后扫,看有没有更肥的能超过它。
外层扫描 · 发现第二片水域,起点 (1,0)：外层扫描继续往后走,前面捞过的水域格都已经被置成 0、当成陆地跳过了。现在碰到还没动过的水域 (1,0),里面有 4 条鱼,这是第二片水域的起点,又发起一次 DFS,本片渔获从 4 起步。
从 (1,0) 看四邻 · 下边是水域：站在起点 (1,0),按上右下左的顺序看四个邻居。别的方向要么出界、要么是陆地 0,只有下边的 (2,0) 是相连的水域、还没捞过。DFS 的规矩就是先钻进这条路走到底,所以下一步游到 (2,0)。
游到 (2,0) · 再捞 1 条：顺着相连水域游到 (2,0),把这里的 1 条也捞走,当前格立刻置 0 当访问标记,免得回头重捞。本片渔获累加到 5 条。它四周再没有新的相连水域了,这一片就到此为止。
第二片走完 · 本片总渔获 = 5：这一片相连水域走完了,一共 2 个格子,鱼数加起来是 5 条。这就是渔夫从这片里出发能捞到的全部。接下来把它和目前记下的最优渔获比一比。
第二片结算 · 刷新最优：本片 5 条,比之前的最优 3 条还多,那就刷新纪录。把这一片标成绿色表示它是当前最肥的一片,当前最优渔获更新成 5 条。之前领先的那片退成灰蓝,不再是冠军。
外层扫描 · 发现第三片水域,起点 (1,3)：外层扫描继续往后走,前面捞过的水域格都已经被置成 0、当成陆地跳过了。现在碰到还没动过的水域 (1,3),里面有 3 条鱼,这是第三片水域的起点,又发起一次 DFS,本片渔获从 3 起步。
从 (1,3) 看四邻 · 下边是水域：站在起点 (1,3),按上右下左的顺序看四个邻居。别的方向要么出界、要么是陆地 0,只有下边的 (2,3) 是相连的水域、还没捞过。DFS 的规矩就是先钻进这条路走到底,所以下一步游到 (2,3)。
游到 (2,3) · 再捞 4 条：顺着相连水域游到 (2,3),把这里的 4 条也捞走,当前格立刻置 0 当访问标记,免得回头重捞。本片渔获累加到 7 条。它四周再没有新的相连水域了,这一片就到此为止。
第三片走完 · 本片总渔获 = 7：这一片相连水域走完了,一共 2 个格子,鱼数加起来是 7 条。这就是渔夫从这片里出发能捞到的全部。接下来把它和目前记下的最优渔获比一比。
第三片结算 · 刷新最优：本片 7 条,比之前的最优 5 条还多,那就刷新纪录。把这一片标成绿色表示它是当前最肥的一片,当前最优渔获更新成 7 条。之前领先的那片退成灰蓝,不再是冠军。
外层扫描 · 发现第四片水域,起点 (3,1)：外层扫描继续往后走,前面捞过的水域格都已经被置成 0、当成陆地跳过了。现在碰到还没动过的水域 (3,1),里面有 3 条鱼,这是第四片水域的起点,又发起一次 DFS,本片渔获从 3 起步。
从 (3,1) 看四邻 · 右边是水域：站在起点 (3,1),按上右下左的顺序看四个邻居。别的方向要么出界、要么是陆地 0,只有右边的 (3,2) 是相连的水域、还没捞过。DFS 的规矩就是先钻进这条路走到底,所以下一步游到 (3,2)。
游到 (3,2) · 再捞 2 条：顺着相连水域游到 (3,2),把这里的 2 条也捞走,当前格立刻置 0 当访问标记,免得回头重捞。本片渔获累加到 5 条。它四周再没有新的相连水域了,这一片就到此为止。
第四片走完 · 本片总渔获 = 5：这一片相连水域走完了,一共 2 个格子,鱼数加起来是 5 条。这就是渔夫从这片里出发能捞到的全部。接下来把它和目前记下的最优渔获比一比。
第四片结算 · 未超最优：本片 5 条,没能超过当前最优的 7 条,纪录保持不变。把这一片也标成灰蓝表示已经查完、出局,当前最优渔获仍然是 7 条。继续扫剩下的格子。
回放 · 四片 3 / 5 / 7 / 5,最大 7：全图扫完,四片水域的鱼总数分别是 3、5、7、5。渔夫一趟只能待在一片里,自然挑最肥的那片,也就是右中那片绿色的 7 条。判定始终只看一件事:同一片相连水域的鱼求和,不同片之间取最大。答案就是 7。
边界想清:全陆地记 0、单水域格记它自己的鱼数、多个孤立单格取最大而非求和。
面试重点:逐片洪水填充片内求和、可换 BFS 或并查集、时间空间都是 O(m 乘 n)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *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(m·n)，m 行 n 列共 m 乘 n 个格子。外层扫一遍每个格子,每个水域格被某次 DFS 恰好访问并置 0 一次,每格只看四个固定方向,都是常数操作,整体随格子总数线性增长
- 空间：O(m·n)，按峰值算。原地把网格当访问标记不额外开表;递归栈深度最坏是一整片水域铺满整张网格时,栈里排到接近 m 乘 n 个格子。峰值就是 O(m·n),不随面积平方增长
易错点
面试追问把动画讲成自己的话
追问这题的核心思路是什么?
追问除了 DFS,还能怎么做?
追问为什么时间是线性,空间又是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
统计完全连通分量的数量
LeetCode 2685 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题