LeetCode 2658中等图 · 网格

网格图中鱼的最大数目图解题解

这道题到底在问什么

给定一张 m 行 n 列的网格。格子值为 0 是陆地,大于 0 是水域,值就是这格的鱼数。渔夫从任一水域格出发,可以反复选择捞光当前格的鱼,或移动到四方向相邻的水域格。求最优策略下最多能捞到的鱼数;没有水域返回 0。

输入: grid=[[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
输出: 7
输入: grid=[[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
输出: 1

最优解：一步一步想明白

3记牢这一句:片内求和,片间取最大。同一片相连水域的鱼要全部加起来,不同片之间则是挑总和最大的那一片。下面从左上角开始,一片一片地捞。
4目标:最大单片渔获这是工作网格。写着数字的是水域格,数字就是鱼数;写着点的是陆地格,值为 0,渔夫过不去。一眼看去,数字被点分隔成了四小簇:左上两格、左中两格、右中两格、下方两格。接下来就把这四片逐一走一遍,每走完一片记下它的鱼总数,再挑出最大的那一片。
5第一片开工外层循环从左上角开始逐格扫。跳过所有陆地,第一个碰到的水域是 (0,1),里面有 2 条鱼。以它为起点发起一次 DFS,先把这 2 条记进本片渔获,再顺着相连水域往外扩。
6沿右边深入站在起点 (0,1),按上右下左的顺序看四个邻居。别的方向要么出界、要么是陆地 0,只有右边的 (0,2) 是相连的水域、还没捞过。DFS 的规矩就是先钻进这条路走到底,所以下一步游到 (0,2)。
7本片累计 3顺着相连水域游到 (0,2),把这里的 1 条也捞走,当前格立刻置 0 当访问标记,免得回头重捞。本片渔获累加到 3 条。它四周再没有新的相连水域了,这一片就到此为止。
8本片渔获 3这一片相连水域走完了,一共 2 个格子,鱼数加起来是 3 条。这就是渔夫从这片里出发能捞到的全部。接下来把它和目前记下的最优渔获比一比。
9刷新最优 = 3这是扫到的第一片水域,一共 3 条,还没有别的片能比。它直接成为当前最优,把这一片标成绿色表示它是眼下最肥的一片,当前最优渔获记成 3 条。接着往后扫,看有没有更肥的能超过它。
10第二片开工外层扫描继续往后走,前面捞过的水域格都已经被置成 0、当成陆地跳过了。现在碰到还没动过的水域 (1,0),里面有 4 条鱼,这是第二片水域的起点,又发起一次 DFS,本片渔获从 4 起步。
11沿下边深入站在起点 (1,0),按上右下左的顺序看四个邻居。别的方向要么出界、要么是陆地 0,只有下边的 (2,0) 是相连的水域、还没捞过。DFS 的规矩就是先钻进这条路走到底,所以下一步游到 (2,0)。
12本片累计 5顺着相连水域游到 (2,0),把这里的 1 条也捞走,当前格立刻置 0 当访问标记,免得回头重捞。本片渔获累加到 5 条。它四周再没有新的相连水域了,这一片就到此为止。
13本片渔获 5这一片相连水域走完了,一共 2 个格子,鱼数加起来是 5 条。这就是渔夫从这片里出发能捞到的全部。接下来把它和目前记下的最优渔获比一比。
14刷新最优 = 5本片 5 条,比之前的最优 3 条还多,那就刷新纪录。把这一片标成绿色表示它是当前最肥的一片,当前最优渔获更新成 5 条。之前领先的那片退成灰蓝,不再是冠军。
15第三片开工外层扫描继续往后走,前面捞过的水域格都已经被置成 0、当成陆地跳过了。现在碰到还没动过的水域 (1,3),里面有 3 条鱼,这是第三片水域的起点,又发起一次 DFS,本片渔获从 3 起步。
16沿下边深入站在起点 (1,3),按上右下左的顺序看四个邻居。别的方向要么出界、要么是陆地 0,只有下边的 (2,3) 是相连的水域、还没捞过。DFS 的规矩就是先钻进这条路走到底,所以下一步游到 (2,3)。
17本片累计 7顺着相连水域游到 (2,3),把这里的 4 条也捞走,当前格立刻置 0 当访问标记,免得回头重捞。本片渔获累加到 7 条。它四周再没有新的相连水域了,这一片就到此为止。
18本片渔获 7这一片相连水域走完了,一共 2 个格子,鱼数加起来是 7 条。这就是渔夫从这片里出发能捞到的全部。接下来把它和目前记下的最优渔获比一比。
19刷新最优 = 7本片 7 条,比之前的最优 5 条还多,那就刷新纪录。把这一片标成绿色表示它是当前最肥的一片,当前最优渔获更新成 7 条。之前领先的那片退成灰蓝,不再是冠军。
20第四片开工外层扫描继续往后走,前面捞过的水域格都已经被置成 0、当成陆地跳过了。现在碰到还没动过的水域 (3,1),里面有 3 条鱼,这是第四片水域的起点,又发起一次 DFS,本片渔获从 3 起步。
21沿右边深入站在起点 (3,1),按上右下左的顺序看四个邻居。别的方向要么出界、要么是陆地 0,只有右边的 (3,2) 是相连的水域、还没捞过。DFS 的规矩就是先钻进这条路走到底,所以下一步游到 (3,2)。
22本片累计 5顺着相连水域游到 (3,2),把这里的 2 条也捞走,当前格立刻置 0 当访问标记,免得回头重捞。本片渔获累加到 5 条。它四周再没有新的相连水域了,这一片就到此为止。
23本片渔获 5这一片相连水域走完了,一共 2 个格子,鱼数加起来是 5 条。这就是渔夫从这片里出发能捞到的全部。接下来把它和目前记下的最优渔获比一比。
24最优保持 7本片 5 条,没能超过当前最优的 7 条,纪录保持不变。把这一片也标成灰蓝表示已经查完、出局,当前最优渔获仍然是 7 条。继续扫剩下的格子。
25答案 = 7全图扫完,四片水域的鱼总数分别是 3、5、7、5。渔夫一趟只能待在一片里,自然挑最肥的那片,也就是右中那片绿色的 7 条。判定始终只看一件事:同一片相连水域的鱼求和,不同片之间取最大。答案就是 7。

⚠️ 容易写错的地方

✗ 错：把所有水域格的鱼一股脑加起来当答案

✓ 对：只把同一片相连水域的鱼求和,片间取最大

陆地把水域切成互不相通的片,渔夫一趟只能困在一片里,答案是单片和的最大值而非全图总和

✗ 错：进入水域格却忘了置 0

✓ 对：进格第一步就把它置 0 当访问标记

不置 0 会顺着来回相邻的两格无限递归,或把同一格重复计数,鱼数偏大甚至栈溢出

✗ 错：外层只从某个固定角落发起一次搜索

✓ 对：外层要扫遍每个格子,对每个没捞过的水域都发起 DFS

水域被切成多片,只搜一次会漏掉其它片,必须逐格扫描才能覆盖所有片

✗ 错：把陆地格也当成可以游过去

✓ 对：只朝值大于 0 的相邻格递归

值为 0 是陆地,渔夫过不去,踩进去既走不通也会把不相连的片错误接到一起

完整代码（Python / C++ / Java）

Python

from __future__ import annotations
from 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int findMaxFish(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;
        function<int(int, int)> dfs = [&](int i, int j) -> int {
            int cnt = grid[i][j];
            grid[i][j] = 0;
            int dirs[5] = {-1, 0, 1, 0, -1};
            for (int k = 0; k < 4; ++k) {
                int x = i + dirs[k], y = j + dirs[k + 1];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {
                    cnt += dfs(x, y);
                }
            }
            return cnt;
        };
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j]) {
                    ans = max(ans, dfs(i, j));
                }
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    private int[][] grid;
    private int m;
    private int n;

    public int findMaxFish(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] > 0) {
                    ans = Math.max(ans, dfs(i, j));
                }
            }
        }
        return ans;
    }

    private int dfs(int i, int j) {
        int cnt = grid[i][j];
        grid[i][j] = 0;
        int[] dirs = {-1, 0, 1, 0, -1};
        for (int k = 0; k < 4; ++k) {
            int x = i + dirs[k], y = j + dirs[k + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0) {
                cnt += dfs(x, y);
            }
        }
        return cnt;
    }
}

复杂度

时间

O(m·n)

m 行 n 列共 m 乘 n 个格子。外层扫一遍每个格子,每个水域格被某次 DFS 恰好访问并置 0 一次,每格只看四个固定方向,都是常数操作,整体随格子总数线性增长

空间

O(m·n)

按峰值算。原地把网格当访问标记不额外开表;递归栈深度最坏是一整片水域铺满整张网格时,栈里排到接近 m 乘 n 个格子。峰值就是 O(m·n),不随面积平方增长

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着网格图中鱼的最大数目的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

这题的核心思路是什么?+

陆地把水域切成互不相通的连通片,渔夫一趟只能困在一片里,能捞到的就是这一片的鱼总和。所以在网格上逐片做洪水填充:外层逐格扫,遇到没捞过的水域格就发起 DFS,沿四方向把整片走遍、鱼数求和,一路把走过的格子置 0 当访问标记。用每一片的总和去刷新最大值,扫完全图就是答案。

除了 DFS,还能怎么做?+

可以把 DFS 换成 BFS,用队列一圈圈扩散同一片水域,鱼数累加逻辑不变。也可以用并查集,把相邻的水域格合并成同一个集合,同时维护每个集合的鱼数总和,最后取所有集合和的最大值。三种做法复杂度都是格子数量级,DFS 洪水填充写起来最直接。

为什么时间是线性,空间又是多少?+

每个水域格只会被某次 DFS 访问并置 0 一次,外层再扫一遍,加起来每格常数次操作,时间是 O(m 乘 n)。空间按峰值算:原地把网格当访问标记不额外开表,递归栈最坏在一整片水域铺满网格时排到接近 m 乘 n 个格子,所以空间是 O(m 乘 n)。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把网格图中鱼的最大数目一步步讲透（全站 0 节语音精讲，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 2658中等图 · 网格

网格图中鱼的最大数目图解题解

这道题到底在问什么

输入: grid=[[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
输出: 7
输入: grid=[[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
输出: 1

最优解：一步一步想明白

3记牢这一句:片内求和,片间取最大。同一片相连水域的鱼要全部加起来,不同片之间则是挑总和最大的那一片。下面从左上角开始,一片一片地捞。
4目标:最大单片渔获这是工作网格。写着数字的是水域格,数字就是鱼数;写着点的是陆地格,值为 0,渔夫过不去。一眼看去,数字被点分隔成了四小簇:左上两格、左中两格、右中两格、下方两格。接下来就把这四片逐一走一遍,每走完一片记下它的鱼总数,再挑出最大的那一片。
5第一片开工外层循环从左上角开始逐格扫。跳过所有陆地,第一个碰到的水域是 (0,1),里面有 2 条鱼。以它为起点发起一次 DFS,先把这 2 条记进本片渔获,再顺着相连水域往外扩。
6沿右边深入站在起点 (0,1),按上右下左的顺序看四个邻居。别的方向要么出界、要么是陆地 0,只有右边的 (0,2) 是相连的水域、还没捞过。DFS 的规矩就是先钻进这条路走到底,所以下一步游到 (0,2)。
7本片累计 3顺着相连水域游到 (0,2),把这里的 1 条也捞走,当前格立刻置 0 当访问标记,免得回头重捞。本片渔获累加到 3 条。它四周再没有新的相连水域了,这一片就到此为止。
8本片渔获 3这一片相连水域走完了,一共 2 个格子,鱼数加起来是 3 条。这就是渔夫从这片里出发能捞到的全部。接下来把它和目前记下的最优渔获比一比。
9刷新最优 = 3这是扫到的第一片水域,一共 3 条,还没有别的片能比。它直接成为当前最优,把这一片标成绿色表示它是眼下最肥的一片,当前最优渔获记成 3 条。接着往后扫,看有没有更肥的能超过它。
10第二片开工外层扫描继续往后走,前面捞过的水域格都已经被置成 0、当成陆地跳过了。现在碰到还没动过的水域 (1,0),里面有 4 条鱼,这是第二片水域的起点,又发起一次 DFS,本片渔获从 4 起步。
11沿下边深入站在起点 (1,0),按上右下左的顺序看四个邻居。别的方向要么出界、要么是陆地 0,只有下边的 (2,0) 是相连的水域、还没捞过。DFS 的规矩就是先钻进这条路走到底,所以下一步游到 (2,0)。
12本片累计 5顺着相连水域游到 (2,0),把这里的 1 条也捞走,当前格立刻置 0 当访问标记,免得回头重捞。本片渔获累加到 5 条。它四周再没有新的相连水域了,这一片就到此为止。
13本片渔获 5这一片相连水域走完了,一共 2 个格子,鱼数加起来是 5 条。这就是渔夫从这片里出发能捞到的全部。接下来把它和目前记下的最优渔获比一比。
14刷新最优 = 5本片 5 条,比之前的最优 3 条还多,那就刷新纪录。把这一片标成绿色表示它是当前最肥的一片,当前最优渔获更新成 5 条。之前领先的那片退成灰蓝,不再是冠军。
15第三片开工外层扫描继续往后走,前面捞过的水域格都已经被置成 0、当成陆地跳过了。现在碰到还没动过的水域 (1,3),里面有 3 条鱼,这是第三片水域的起点,又发起一次 DFS,本片渔获从 3 起步。
16沿下边深入站在起点 (1,3),按上右下左的顺序看四个邻居。别的方向要么出界、要么是陆地 0,只有下边的 (2,3) 是相连的水域、还没捞过。DFS 的规矩就是先钻进这条路走到底,所以下一步游到 (2,3)。
17本片累计 7顺着相连水域游到 (2,3),把这里的 4 条也捞走,当前格立刻置 0 当访问标记,免得回头重捞。本片渔获累加到 7 条。它四周再没有新的相连水域了,这一片就到此为止。
18本片渔获 7这一片相连水域走完了,一共 2 个格子,鱼数加起来是 7 条。这就是渔夫从这片里出发能捞到的全部。接下来把它和目前记下的最优渔获比一比。
19刷新最优 = 7本片 7 条,比之前的最优 5 条还多,那就刷新纪录。把这一片标成绿色表示它是当前最肥的一片,当前最优渔获更新成 7 条。之前领先的那片退成灰蓝,不再是冠军。
20第四片开工外层扫描继续往后走,前面捞过的水域格都已经被置成 0、当成陆地跳过了。现在碰到还没动过的水域 (3,1),里面有 3 条鱼,这是第四片水域的起点,又发起一次 DFS,本片渔获从 3 起步。
21沿右边深入站在起点 (3,1),按上右下左的顺序看四个邻居。别的方向要么出界、要么是陆地 0,只有右边的 (3,2) 是相连的水域、还没捞过。DFS 的规矩就是先钻进这条路走到底,所以下一步游到 (3,2)。
22本片累计 5顺着相连水域游到 (3,2),把这里的 2 条也捞走,当前格立刻置 0 当访问标记,免得回头重捞。本片渔获累加到 5 条。它四周再没有新的相连水域了,这一片就到此为止。
23本片渔获 5这一片相连水域走完了,一共 2 个格子,鱼数加起来是 5 条。这就是渔夫从这片里出发能捞到的全部。接下来把它和目前记下的最优渔获比一比。
24最优保持 7本片 5 条,没能超过当前最优的 7 条,纪录保持不变。把这一片也标成灰蓝表示已经查完、出局,当前最优渔获仍然是 7 条。继续扫剩下的格子。
25答案 = 7全图扫完,四片水域的鱼总数分别是 3、5、7、5。渔夫一趟只能待在一片里,自然挑最肥的那片,也就是右中那片绿色的 7 条。判定始终只看一件事:同一片相连水域的鱼求和,不同片之间取最大。答案就是 7。

⚠️ 容易写错的地方

✗ 错：把所有水域格的鱼一股脑加起来当答案

✓ 对：只把同一片相连水域的鱼求和,片间取最大

陆地把水域切成互不相通的片,渔夫一趟只能困在一片里,答案是单片和的最大值而非全图总和

✗ 错：进入水域格却忘了置 0

✓ 对：进格第一步就把它置 0 当访问标记

不置 0 会顺着来回相邻的两格无限递归,或把同一格重复计数,鱼数偏大甚至栈溢出

✗ 错：外层只从某个固定角落发起一次搜索

✓ 对：外层要扫遍每个格子,对每个没捞过的水域都发起 DFS

水域被切成多片,只搜一次会漏掉其它片,必须逐格扫描才能覆盖所有片

✗ 错：把陆地格也当成可以游过去

✓ 对：只朝值大于 0 的相邻格递归

值为 0 是陆地,渔夫过不去,踩进去既走不通也会把不相连的片错误接到一起

完整代码（Python / C++ / Java）

Python

from __future__ import annotations
from 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int findMaxFish(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;
        function<int(int, int)> dfs = [&](int i, int j) -> int {
            int cnt = grid[i][j];
            grid[i][j] = 0;
            int dirs[5] = {-1, 0, 1, 0, -1};
            for (int k = 0; k < 4; ++k) {
                int x = i + dirs[k], y = j + dirs[k + 1];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {
                    cnt += dfs(x, y);
                }
            }
            return cnt;
        };
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j]) {
                    ans = max(ans, dfs(i, j));
                }
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    private int[][] grid;
    private int m;
    private int n;

    public int findMaxFish(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] > 0) {
                    ans = Math.max(ans, dfs(i, j));
                }
            }
        }
        return ans;
    }

    private int dfs(int i, int j) {
        int cnt = grid[i][j];
        grid[i][j] = 0;
        int[] dirs = {-1, 0, 1, 0, -1};
        for (int k = 0; k < 4; ++k) {
            int x = i + dirs[k], y = j + dirs[k + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0) {
                cnt += dfs(x, y);
            }
        }
        return cnt;
    }
}

复杂度

时间

O(m·n)

空间

O(m·n)

看不够？换成动画再走一遍

看交互动画版 →更多图解题

面试官可能追问

这题的核心思路是什么?+

除了 DFS,还能怎么做?+

为什么时间是线性,空间又是多少?+

想听吴师兄把这道题讲给你听？

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

网格图中鱼的最大数目 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

网格图中鱼的最大数目 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

网格图中鱼的最大数目图解题解

网格图中鱼的最大数目图解题解