网格图中鱼的最大数目

标签: 深度优先搜索 广度优先搜索 并查集 数组 矩阵

难度: 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

Submission

运行时间: 65 ms

内存: 16.3 MB

class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        ans=0
        global p
        p=0
        n,m=len(grid),len(grid[0])
        def dfs(i,j):
            global p
            if i<0 or j<0 or i>=n or j>=m or grid[i][j]==0:
                return
            p+=grid[i][j]
            grid[i][j]=0
            dfs(i+1,j)
            dfs(i-1,j)
            dfs(i,j+1)
            dfs(i,j-1)
        for i in range(n):
            for j in range(m):
                if grid[i][j]:
                    p=0
                    dfs(i,j)
                    ans=max(ans,p)
        return ans

Explain

此题目要求计算渔夫在最优策略下能捕获的最大鱼数。基本思路是采用深度优先搜索(DFS)，遍历每一个水域单元格，并计算从该单元格出发能够访问到的所有相连水域单元格中的鱼的总数。针对每个水域，我们执行DFS，标记访问过的单元格为陆地（即设置为0），以避免重复访问。每次DFS都会更新一个全局变量来记录当前连通水域中的总鱼数，并与全局最大值进行比较更新。这样，遍历完整个网格后，全局最大值即为所求的最大鱼数。

时间复杂度: O(m*n)

空间复杂度: O(m*n)

class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        ans = 0  # 最大鱼数初始化为0
        global p  # 全局变量p用于记录当前连通水域的鱼的总数
        p = 0
        n, m = len(grid), len(grid[0])  # 网格的行数和列数
        def dfs(i, j):
            global p
            # 边界检查以及是否为陆地的检查
            if i < 0 or j < 0 or i >= n or j >= m or grid[i][j] == 0:
                return
            p += grid[i][j]  # 累加当前单元格的鱼数
            grid[i][j] = 0  # 标记当前单元格为已访问
            # 向四个方向递归搜索
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)
        for i in range(n):
            for j in range(m):
                if grid[i][j]:  # 只对水域单元格进行处理
                    p = 0  # 每次开始新的水域连通区域前，重置p
                    dfs(i, j)  # 从当前单元格开始DFS
                    ans = max(ans, p)  # 更新最大鱼数
        return ans

Explore

深度优先搜索(DFS)因其递归实现的简洁性和在处理连通分量问题时的高效性而被选用。DFS在访问每个连通的水域单元格时能够快速深入，并在遇到边界时回溯，这使得它在找到所有连通水域时非常有效。此外，DFS通常需要较少的内存空间，因为它不需要像BFS那样存储所有层级的节点。尽管BFS也可以应用于此问题，但DFS在代码实现和理解上更为直接。

将已访问的水域单元格标记为0的确会修改原始数据结构，这在某些情况下可能不可取，特别是如果需要保留原始网格数据进行其他操作。为了保留原始网格状态，可以使用一个同等大小的辅助数组来记录访问状态，此数组初始全为false，访问过的单元格标记为true。这样可以避免修改原始网格，同时达到标记已访问单元格的目的。

是的，使用全局变量在多线程或并行处理环境中确实可能导致线程安全问题，因为多个线程可能同时修改这个全局变量，从而引起数据不一致的问题。为了避免这种情况，可以将全局变量`p`改为局部变量，并通过函数参数传递的方式在递归调用中维护其状态，或者使用线程局部存储来确保每个线程对其有一个单独的副本。

题解中没有特别提到对这种情况的优化。在处理大型数据集或深度极大的连通区域时，确实存在栈溢出的风险。一种可能的优化方法是使用非递归的DFS实现，即使用显式的栈来模拟递归过程。这种方法可控制栈的大小，避免了系统栈溢出的问题。另一种方法是限制递归深度或在DFS前进行预处理，如剪枝，以减少不必要的递归调用。