2658 - Maximum Number of Fish in a Grid

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 the maximum 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

Solution 1: DFS

JAVA

• 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;
      }
  }

C++

• 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;
      }
  };

PYTHON

• class Solution:
      def findMaxFish(self, grid):
          self.m, self.n = len(grid), len(grid[0])
          self.grid = grid
          ans = 0
  
          for i in range(self.m):
              for j in range(self.n):
                  if grid[i][j] > 0:
                      ans = max(ans, self.dfs(i, j))
          
          return ans
  
      def dfs(self, i, j):
          cnt = self.grid[i][j]
          self.grid[i][j] = 0  # Mark the cell as visited
          dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
  
          for dx, dy in dirs:
              x, y = i + dx, j + dy
              if 0 <= x < self.m and 0 <= y < self.n and self.grid[x][y] > 0:
                  cnt += self.dfs(x, y)
          
          return cnt