Maximum Number of Fish in a Grid

Problem Description

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.

Key Insights

• The problem can be solved using Depth-First Search (DFS) or Breadth-First Search (BFS) to explore all connected water cells.
• Each connected component of water cells can be treated as a separate area where fish can be collected.
• The total number of fish in a connected component can be calculated by traversing each cell in the component and summing up the fish counts.

Space and Time Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid, as we may need to visit each cell once.

Space Complexity: O(m * n), for the visited matrix and the recursion stack in the case of DFS.

Solution

To solve the problem, we can use either DFS or BFS to traverse all connected water cells starting from each unvisited water cell. For each connected component, we will calculate the total number of fish and keep track of the maximum found.

1. Iterate through each cell in the grid.
2. If the cell is a water cell and has not been visited, start a DFS/BFS from that cell.
3. During the traversal, mark cells as visited and sum the total fish in the connected component.
4. Compare the total with a running maximum and update if necessary.
5. Return the maximum number of fish found.

Code Solutions