Question

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

English Version

题目描述

给你一个下标从 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(i, j)$，表示从网格图中的第 $i$ 行第 $j$ 列的格子出发，可以捕捞到的最大鱼数。函数 $dfs(i, j)$ 的执行逻辑如下：

我们用一个变量 $cnt$ 来记录当前格子中的鱼的数目，然后将当前格子中的鱼的数目置为 $0$，表示已经捕捞过了。然后我们遍历当前格子的上下左右四个方向，如果某个方向的格子 $(x, y)$ 在网格图内且是水域格子，那么我们就递归调用 $dfs(x, y)$ 函数，将返回值加到 $cnt$ 中。最后返回 $cnt$ 即可。

在主函数中，我们遍历所有的格子 $(i, j)$，如果当前格子是水域格子，那么我们就调用 $dfs(i, j)$ 函数，取返回值的最大值作为答案返回即可。

时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。其中 $m$ 和 $n$ 分别是网格图的行数和列数。

class Solution:
  def findMaxFish(self, grid: List[List[int]]) -> int:
    def dfs(i: int, j: int) -> int:
      cnt = grid[i][j]
      grid[i][j] = 0
      for a, b in pairwise((-1, 0, 1, 0, -1)):
        x, y = i + a, j + b
        if 0 <= x < m and 0 <= y < n and grid[x][y]:
          cnt += dfs(x, y)
      return cnt

    m, n = len(grid), len(grid[0])
    ans = 0
    for i in range(m):
      for j in range(n):
        if grid[i][j]:
          ans = max(ans, dfs(i, j))
    return ans

class Solution {
  private int[][] grid;
  private int m;
  private int n;

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

  private int dfs(int i, int j) {
    int cnt = grid[i][j];
    grid[i][j] = 0;
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int k = 0; k < 4; ++k) {
      int x = i + dirs[k], y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0) {
        cnt += dfs(x, y);
      }
    }
    return cnt;
  }
}

class Solution {
public:
  int findMaxFish(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    int ans = 0;
    function<int(int, int)> dfs = [&](int i, int j) -> int {
      int cnt = grid[i][j];
      grid[i][j] = 0;
      int dirs[5] = {-1, 0, 1, 0, -1};
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k], y = j + dirs[k + 1];
        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {
          cnt += dfs(x, y);
        }
      }
      return cnt;
    };
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j]) {
          ans = max(ans, dfs(i, j));
        }
      }
    }
    return ans;
  }
};

func findMaxFish(grid [][]int) (ans int) {
  m, n := len(grid), len(grid[0])
  dirs := [5]int{-1, 0, 1, 0, -1}
  var dfs func(i, j int) int
  dfs = func(i, j int) int {
    cnt := grid[i][j]
    grid[i][j] = 0
    for k := 0; k < 4; k++ {
      x, y := i+dirs[k], j+dirs[k+1]
      if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0 {
        cnt += dfs(x, y)
      }
    }
    return cnt
  }
  for i := range grid {
    for j := range grid[i] {
      if grid[i][j] > 0 {
        ans = max(ans, dfs(i, j))
      }
    }
  }
  return
}

function findMaxFish(grid: number[][]): number {
  const m = grid.length;
  const n = grid[0].length;

  const dirs = [-1, 0, 1, 0, -1];
  const dfs = (i: number, j: number): number => {
    let cnt = grid[i][j];
    grid[i][j] = 0;
    for (let k = 0; k < 4; ++k) {
      const x = i + dirs[k];
      const y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0) {
        cnt += dfs(x, y);
      }
    }
    return cnt;
  };

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