🛫 网格图中鱼的最大数目

📝 题目描述

​ 给你一个下标从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)，前提是相邻格子在网格图内。

📋 代码模板

java

class Solution {
    public int findMaxFish(int[][] grid) {

    }
}

typescript

function findMaxFish(grid: number[][]): number {

}

💡 提示

1. $m==grid.length$
2. $n==grid[i].length$
3. $1\le m\le 10$
4. $1\le n\le 10$
5. $0\le grid[i][j]\le 10$

🚀 示例

示例一

​ 输入grid为[[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]，输出为7。渔夫总共有 $4$ 种方案，分别捕捞 $2+1=3$、$4+1=5$、$3+2=5$、$3+4=7$ 条鱼，最大值为 $7$，示意图如下所示。

示例二

​ 输入grid为[[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]，输出为1。渔夫总共有 $2$ 种方案，分别捕捞 $1$、$1$ 条鱼，最大值为 $1$，示意图如下所示。

示例三

​ 输入grid为[[1,3,0,0,0,0],[7,5,2,0,0,5],[0,0,1,0,0,38],[0,0,4,7,8,0]]，输出为43。渔夫总共有 $2$ 种方案，分别捕捞 $1+3+7+5+2+1+4+7+8=38$、$5+38=43$ 条鱼，最大值为 $43$，示意图如下所示。

🖊️ 题解

​ 该题本质上是在网格中找各个连通块的元素总和，并取最大值作为答案。

​ 我们可以初始化一个值为 $0$ 的最大捕捞鱼数 $maxFish$，并扫描整个二维网格，如果单元格的值大于 $0$，则以它为起始节点进行DFS或BFS。在搜索过程中，每遇到一个尚未访问过的水域单元格（值大于 $0$），就将其所属的连通分量元素总和加上该单元格上的值，并将该单元格标记为”已访问“。在搜索结束后，在当前连通分量元素总和与 $maxFish$ 中选择一个较大值，并更新到变量 $maxFish$ 中。

​ 为了进一步节省算法的空间，我们可以直接将网格中单元格的值更新为 $-1$，表示其已经被访问。

DFS

java

class Solution {
    private final static int[][] DIRS = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private final static int VISITED = -1;

    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));
                }
            }
        }
        return maxFish;
    }

    private int dfs(int[][] grid, int i, int j) {
        if (i < 0 || i > grid.length - 1 || j < 0 || j > grid[0].length - 1
                || grid[i][j] <= 0) {
            return 0;
        }
        int fishes = grid[i][j];
        grid[i][j] = VISITED;
        for (int d = 0; d < 4; d++) {
            fishes += dfs(grid, i + DIRS[d][0], j + DIRS[d][1]);
        }
        return fishes;
    }
}

typescript

const DIRS: number[][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
const VISITED = -1;

function findMaxFish(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const dfs = (i: number, j: number): number => {
        if (i < 0 || i > grid.length - 1 || j < 0 || j > grid[0].length - 1
            || grid[i][j] <= 0) {
            return 0;
        }
        let fishes = grid[i][j];
        grid[i][j] = VISITED;
        for (let d = 0; d < 4; d++) {
            fishes += dfs(i + DIRS[d][0], j + DIRS[d][1]);
        }
        return fishes;
    }
    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;
}

BFS

java

class Solution {
    private final static int[][] DIRS = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private final static int VISITED = -1;

    public int findMaxFish(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int maxFish = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) {
                    int fishes = grid[i][j];
                    queue.offer(new int[]{i, j});
                    grid[i][j] = VISITED;
                    while (!queue.isEmpty()) {
                        int[] cell = queue.poll();
                        int oldI = cell[0], oldJ = cell[1];
                        for (int d = 0; d < 4; d++) {
                            int currentI = oldI + DIRS[d][0], currentJ = oldJ + DIRS[d][1];
                            if (currentI >= 0 && currentI < m && currentJ >= 0 && currentJ < n
                                    && grid[currentI][currentJ] > 0) {
                                fishes += grid[currentI][currentJ];
                                queue.offer(new int[]{currentI, currentJ});
                                grid[currentI][currentJ] = VISITED;
                            }
                        }
                    }
                    maxFish = Math.max(maxFish, fishes);
                }
            }
        }
        return maxFish;
    }
}

typescript

const DIRS: number[][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];
const VISITED = -1;

function findMaxFish(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const queue: number[][] = [];
    let maxFish = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] > 0) {
                let fishes = grid[i][j];
                queue.push([i, j]);
                grid[i][j] = VISITED;
                while (queue.length > 0) {
                    const cell: number[] = queue.shift()!;
                    const oldI = cell[0], oldJ = cell[1];
                    for (let d = 0; d < 4; d++) {
                        const currentI = oldI + DIRS[d][0], currentJ = oldJ + DIRS[d][1];
                        if (currentI >= 0 && currentI < m && currentJ >= 0 && currentJ < n
                            && grid[currentI][currentJ] > 0) {
                            fishes += grid[currentI][currentJ];
                            queue.push([currentI, currentJ]);
                            grid[currentI][currentJ] = VISITED;
                        }
                    }
                }
                maxFish = Math.max(maxFish, fishes);
            }
        }
    }
    return maxFish;
}

💭 复杂度分析

​ 基于DFS的解决方案的复杂度分析如下。

• 时间复杂度：$O(mn)$。其中 $m$ 与 $n$ 分别为网格的行数和列数。
• 空间复杂度：$O(mn)$。在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 $mn$。

​ 基于BFS的解决方案的复杂度分析如下。

• 时间复杂度：$O(mn)$。其中 $m$ 与 $n$ 分别为网格的行数和列数。
• 空间复杂度：$O(mn)$。