题目描述
思路解析
一句话答案：LeetCode 2658 网格中鱼的最大数目：陆地把水域切成互不相通的片，从每个没捞过的水域格发起 DFS 逐片洪水填充求鱼数和，片间取最大，时间 O(m·n)。
渔夫一趟最多能捞多少鱼
给一张 m 行 n 列的网格，格子值为 0 是陆地，大于 0 是水域、数字就是这格的鱼数。渔夫从任一水域格下水，能反复捞光脚下的鱼，也能朝上下左右挪到相邻的水域格，陆地过不去。问一趟最多捞到几条鱼，没有水域就返回 0。题面例子 grid=[[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]，答案是 7。
把所有鱼一股脑加起来，为什么多算了
这张网格里的鱼全加起来共 20 条，可答案只有 7。症结在于渔夫下一次水就困在一处：陆地把水域割成了互不相通的几摊，脚下这摊和隔着陆地的那摊之间根本游不过去。所以能捞的不是全图鱼数，而是渔夫落脚那一摊的鱼数和，真正要求的是所有水摊里鱼数最多的那一摊。
陆地切出几片水域，就逐片称一称
先把相连的水域圈成一片：从一个水域格出发，只要上下左右的邻居也是水域，就顺着游过去，能连成一串的格子都算同一片。这种顺着相邻格子一路蔓延、把一整片走遍的走法就是洪水填充，用 DFS 实现，也就是顺一条路走到底再回头。每走完一片就把这片的鱼数全加起来，得到它的总渔获；全图切成好几片，谁的总渔获最大谁就是答案。
游过的格子随手清零，外层再逐格补扫
DFS 每进一个水域格，第一件事是把鱼数记进本片渔获，紧接着立刻把这格的值改成 0。这个 0 一身两用：既是捞过的凭据，也是访问标记，往后谁再走到它，看见 0 就当陆地跳过，绝不会回头重捞或在相邻两格之间来回无限打转。
外层再拿一个双重循环从左上到右下逐格扫，碰到还大于 0 的格子，说明遇上一片没动过的新水域，就对它发起 DFS，拿返回的本片总鱼数刷新答案最大值。逐格补扫省不得：只从某个角落搜一次，会漏掉被陆地隔开的其它片。
四片水域 3、5、7、5，最肥的那片是 7
拿题面这张图走一遍。外层从左上扫，第一个撞见的水域是 (0,1) 的 2，发起 DFS：记下 2、清零，右邻 (0,2) 还是水域，游过去捞 1、清零，四周再无水域，这片收工，鱼数 2+1=3，最优记 3。
接着扫到 (1,0) 的 4，向下连到 (2,0) 的 1，这片 4+1=5，比 3 大，最优刷成 5。再扫到 (1,3) 的 3，向下连 (2,3) 的 4，这片 3+4=7，最优刷成 7。最后 (3,1) 的 3 向右连 (3,2) 的 2，这片 3+2=5，没超过 7，最优不动。四片是 3、5、7、5，答案就是最大的 7。
复杂度是格子数量级，几处边界先想清
时间 O(m·n)：外层把 m 乘 n 个格子扫一遍，每个水域格只被某次 DFS 访问并清零一次，每格只看四个固定方向，都是常数操作。空间也是 O(m·n)，最坏是一整片水域铺满网格，递归栈一层层压下去，深度逼近格子总数。
剩下几种特殊输入值得提前过一遍。整张图全是陆地、没有水域，直接返回 0。只有一个孤零零的水域格，那片就它自己，答案是它的鱼数。散落着好几个互不相邻的单格水域，答案是其中最大的一个，而不是把它们加起来，它们隔着陆地不属于同一片。至于进格忘了清零，轻则同一格重复计数把鱼数算多，重则相邻两格来回递归停不下来栈溢出。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这一句:片内求和,片间取最大。同一片相连水域的鱼要全部加起来,不同片之间则是挑总和最大的那一片。下面从左上角开始,一片一片地捞。
工作网格 · 水域格写鱼数,陆地写点：这是工作网格。写着数字的是水域格,数字就是鱼数;写着点的是陆地格,值为 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题