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

🟠 🔖 深度优先搜索 广度优先搜索 并查集 数组 矩阵 🔗 力扣open in new window LeetCodeopen in new window

题目

You are given a 0-indexed 2D matrix grid of size m x n, where (r, c) represents:

A land cell if grid[r][c] = 0, or
A water cell containing grid[r][c] fish, if grid[r][c] > 0.

A fisher can start at any water cell (r, c) and can do the following operations any number of times:

Catch all the fish at cell (r, c), or
Move to any adjacent water cell.

Return _themaximum number of fish the fisher can catch if he chooses his starting cell optimally, or _0 if no water cell exists.

An adjacent cell of the cell (r, c), is one of the cells (r, c + 1), (r, c - 1), (r + 1, c) or (r - 1, c) if it exists.

Example 1:

Input: grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
Output: 7
Explanation: The fisher can start at cell (1,3) and collect 3 fish, then move to cell (2,3) and collect 4 fish.

Example 2:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
Output: 1
Explanation: The fisher can start at cells (0,0) or (3,3) and collect a single fish.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 10
0 <= grid[i][j] <= 10

题目大意

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

解题思路

利用深度优先搜索（DFS）探索连通块，记录每个连通块的鱼数量：

遍历网格中的所有格子；
当发现未访问且非零的格子时，以该格子为起点执行 DFS；
- 遇到越界或值为 0 的格子直接返回；
- 将当前格子置零以节省空间（标记为已访问），不使用额外的 visited 数组；
- 向上下左右递归搜索，将结果累加。
累计连通块中的鱼数量，并与当前最大值比较，更新结果；
返回最大值。

复杂度分析

时间复杂度：O(m * n)，每个格子最多访问一次。
空间复杂度：O(m * n)，递归调用栈的空间消耗。

代码

/**
 * @param {number[][]} grid
 * @return {number}
 */
var findMaxFish = function (grid) {
	const m = grid.length;
	const n = grid[0].length;
	const directions = [
		[1, 0],
		[-1, 0],
		[0, 1],
		[0, -1]
	];

	const dfs = (i, j) => {
		if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] === 0) {
			return 0;
		}
		let fish = grid[i][j];
		grid[i][j] = 0; // 标记已访问
		for (let [dx, dy] of directions) {
			fish += dfs(i + dx, j + dy);
		}
		return fish;
	};

	let maxFish = 0;
	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			if (grid[i][j] > 0) {
				maxFish = Math.max(maxFish, dfs(i, j));
			}
		}
	}
	return maxFish;
};

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

# 2658. 网格图中鱼的最大数目

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

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

题目

题目大意

解题思路

复杂度分析

代码

相关题目