2658. 网格中鱼的最大数量 - Number of Fish in a Grid

🎯 问题描述（来源于LeetCode）

描述：
给定一个 m x n 的整数矩阵 grid，其中：

0 表示陆地，不能行走。
正整数表示水域，且该格子中的鱼的数量。
你可以在任意水域格子开始，每次向上、下、左、右移动到相邻的水域格子，收集经过的所有格子中的鱼。
请你计算最多能收集到的鱼的总数。如果不存在水域，返回 0。

说明：

只能在水域格子之间移动（即值为正整数的格子）。
可以多次访问同一个格子吗？不行，题目隐含每个格子只能收集一次（实际上通过访问标记保证）。
水域是四连通的。

示例：

示例 1：

1
2
3

输入: grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
输出: 7
解释: 从左上角水域开始，可收集 2+1=3；从右下角水域开始，可收集 4+3=7；最大值为7。

示例 2：

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

💻 解题思路

思路1：DFS 遍历连通分量并求和

算法步骤

初始化：
- 获取网格尺寸 m, n。
- 创建 visited 二维布尔数组，标记已访问的格子。
- 设置答案 ans = 0。
定义 DFS 函数 dfs(i, j)：
- 返回从 (i, j) 出发能收集到的鱼的总数（包含自身）。
- 标记当前格子为已访问。
- 初始化 total = grid[i][j]。
- 对四个方向的邻居：如果位置合法、未访问且是水域（grid[x][y] > 0），则递归调用 dfs(x, y) 并将返回值累加到 total。
- 返回 total。
遍历格子：
- 对每个格子，如果该格子是水域且未被访问，则调用 dfs(i, j) 得到一个连通分量的总鱼数，并更新 ans = max(ans, 当前总鱼数)。
返回 ans。

思路1：代码实现

from typing import List

class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        ans = 0
        
        def dfs(i, j):
            num = grid[i][j]
            visited[i][j] = True
            for x, y in (i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j):
                if 0 <= x < m and 0 <= y < n and not visited[x][y] and grid[x][y] > 0:
                    num += dfs(x, y)
            return num
        
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x > 0 and not visited[i][j]:
                    ans = max(ans, dfs(i, j))
        return ans