2658：网格图中鱼的最大数目（1489 分）

Ian

2023-04-29 约 463 字预计阅读 1 分钟次阅读

力扣第 103 场双周赛第 3 题

题目

给你一个下标从 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

分析

类似 0695，统计连通块的值之和即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        def find(x):
            if f[x] != x:
                f[x] = find(f[x])
            return f[x]

        def union(x, y):
            f[find(x)]=find(y)

        m, n = len(grid), len(grid[0])
        f = list(range(m*n))
        sz = [x for row in grid for x in row]
        for i, j in product(range(m), range(n)):
            if grid[i][j]:
                if i and grid[i-1][j]:
                    union(i*n+j,(i-1)*n+j)
                if j and grid[i][j-1]:
                    union(i*n+j,i*n+j-1)
        d = defaultdict(int)
        for i, j in product(range(m), range(n)):
            if grid[i][j]:
                d[find(i*n+j)] += grid[i][j]
        return max(d.values(),default=0)

72 ms

目录

2658：网格图中鱼的最大数目（1489 分）

题目

分析

解答