2658-网格图中鱼的最大数目

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:07 2023-09-13 17:01:07 Updated    

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

下午两点【biIibiIi@灵茶山艾府】 直播讲题，记得关注哦~

DFS 统计每个包含正数的连通块的元素和，最大值即为答案。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        def dfs(i: int, j: int) -> int:
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:
                return 0
            s = grid[i][j]
            grid[i][j] = 0  # 标记成访问过
            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):
                s += dfs(x, y)  # 四方向移动
            return s
        return max(max(dfs(i, j) for j in range(n)) for i in range(m))
[sol1-Java]
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 {
    private final static int[][] DIRS = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
    private int[][] grid;

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

    private int dfs(int x, int y) {
        int m = grid.length, n = grid[0].length;
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0)
            return 0;
        int sum = grid[x][y];
        grid[x][y] = 0; // 标记成访问过
        for (var d : DIRS) // 四方向移动
            sum += dfs(x + d[0], y + d[1]);
        return sum;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    static constexpr int dirs[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
public:
    int findMaxFish(vector<vector<int>> &grid) {
        int m = grid.size(), n = grid[0].size(), ans = 0;
        function<int(int, int)> dfs = [&](int x, int y) -> int {
            if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0)
                return 0;
            int sum = grid[x][y];
            grid[x][y] = 0; // 标记成访问过
            for (auto &d: dirs) // 四方向移动
                sum += dfs(x + d[0], y + d[1]);
            return sum;
        };
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                ans = max(ans, dfs(i, j));
        return ans;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var dirs = []struct{ x, y int }{ {-1, 0}, {1, 0}, {0, -1}, {0, 1} }

func findMaxFish(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	var dfs func(int, int) int
	dfs = func(x, y int) int {
		if x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0 {
			return 0
		}
		sum := grid[x][y]
		grid[x][y] = 0 // 标记成访问过
		for _, d := range dirs { // 四方向移动
			sum += dfs(x+d.x, y+d.y)
		}
		return sum
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			ans = max(ans, dfs(i, j))
		}
	}
	return
}

func max(a, b int) int { if a < b { return b }; return a }

复杂度分析

  • 时间复杂度：\mathcal{O}(mn)，其中 m 和 n 分别为 grid 的行数和列数。
  • 空间复杂度：\mathcal{O}(mn)。递归需要 \mathcal{O}(mn) 的栈空间。
 Comments
On this page
2658-网格图中鱼的最大数目
  1. 复杂度分析