Medium

题目描述

给你一个下标从 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.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • 0 <= grid[i][j] <= 10

解题思路

这道题的核心思想是找到连通的水域区域，并计算每个连通区域中鱼的总数，最后返回最大值。

解题思路：

  1. 连通性分析：由于渔夫只能在相邻的水域格子间移动，问题实际上是寻找所有连通的水域区域。
  2. 深度优先搜索（DFS）：对于每个未访问过的水域格子，使用DFS遍历整个连通区域，累计该区域内所有鱼的数量。
  3. 状态标记：为避免重复计算，需要标记已访问过的格子。可以直接修改原数组，将访问过的格子设为0。
  4. 最优解：遍历所有可能的起始点，记录能捕获的最大鱼数。

算法步骤：

  1. 遍历网格中的每个格子
  2. 如果格子包含鱼（值大于0且未访问），从该格子开始DFS
  3. DFS过程中累计当前连通区域的鱼数，并标记访问过的格子
  4. 更新全局最大值
  5. 返回最终结果

这种方法能保证每个水域格子只被访问一次，效率较高。由于网格规模较小（最大10x10），时间复杂度完全可以接受。

代码实现

class Solution {
public:
    int findMaxFish(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int maxFish = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) {
                    maxFish = max(maxFish, dfs(grid, i, j, m, n));
                }
            }
        }
        
        return maxFish;
    }
    
private:
    int dfs(vector<vector<int>>& grid, int r, int c, int m, int n) {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
            return 0;
        }
        
        int fish = grid[r][c];
        grid[r][c] = 0; // 标记为已访问
        
        // 向四个方向探索
        fish += dfs(grid, r + 1, c, m, n);
        fish += dfs(grid, r - 1, c, m, n);
        fish += dfs(grid, r, c + 1, m, n);
        fish += dfs(grid, r, c - 1, m, n);
        
        return fish;
    }
};

class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        max_fish = 0
        
        def dfs(r, c):
            if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0:
                return 0
            
            fish = grid[r][c]
            grid[r][c] = 0  # 标记为已访问
            
            # 向四个方向探索
            fish += dfs(r + 1, c)
            fish += dfs(r - 1, c)
            fish += dfs(r, c + 1)
            fish += dfs(r, c - 1)
            
            return fish
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] > 0:
                    max_fish = max(max_fish, dfs(i, j))
        
        return max_fish

public class Solution {
    public int FindMaxFish(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int maxFish = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) {
                    maxFish = Math.Max(maxFish, DFS(grid, i, j, m, n));
                }
            }
        }
        
        return maxFish;
    }
    
    private int DFS(int[][] grid, int r, int c, int m, int n) {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
            return 0;
        }
        
        int fish = grid[r][c];
        grid[r][c] = 0; // 标记为已访问
        
        // 向四个方向探索
        fish += DFS(grid, r + 1, c, m, n);
        fish += DFS(grid, r - 1, c, m, n);
        fish += DFS(grid, r, c + 1, m, n);
        fish += DFS(grid, r, c - 1, m, n);
        
        return fish;
    }
}

var findMaxFish = function(grid) {
    const m = grid.length, n = grid[0].length;
    let maxFish = 0;
    
    function dfs(r, c) {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m × n)，其中 m 和 n 分别为网格的行数和列数。每个格子最多被访问一次
空间复杂度O(m × n)，主要来自递归调用栈的深度，最坏情况下整个网格都是连通的水域

相关题目