2658. Maximum Number of Fish in a Grid

Problem Description

The problem presents a 2D matrix grid representing a 'fishing grid' where each cell is either land or water. The cells containing water have a non-zero value representing the number of fish present. A cell with the value 0 indicates that it is a land cell, and no fishing can be done there. The objective is to determine the maximum number of fish that a fisher can catch when starting from an optimally chosen water cell. The conditions for fishing are:

• A fisher can harvest all fish from the water cell he is currently on.
• The fisher can move from one water cell to any directly adjacent water cell (up, down, left, right), provided it isn't land.
• The fisher can perform these actions repetitively and in any order.

The desired output is the maximum number of fish that can be caught, with the possibility of a 0 when no water cell (cells with fish) is available.

Intuition

To solve the problem, we need to consider all water regions (areas of connected water cells) and the fish available within them. Since the fisher can only move to adjacent water cells, whenever he moves, he 'engages' a specific water region. It's important to recognize that once a fisher starts fishing in a region, they should catch all the fish in that region before moving to another since returning to a region is not beneficial—fish already caught won't respawn.

We reach an intuitive approach by focusing on the following points:

• Once the fisher starts at a water cell, they should collect all fish in the connected water region.
• We should account for all fish present in a standalone water region in one go—there's no coming back for more once they are caught.
• By iterating over all water cells and simulating this fishing approach, we can find the largest possible catch.

With these points in mind, we turn to Depth-First Search (DFS)—a perfect technique for exploring all cells in a connected region starting from any given water cell. The DFS counts the fish, marks the cells as 0 once visited (to avoid recounting), and moves to adjacent water cells until the entire region is depleted of fish. We keep track of the maximum number of fish caught in any single run of the DFS across the entire grid. By applying this process to each water cell, we can identify the optimal starting cell that yields the most fish.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Solution Approach

To achieve the task, we use a recursive Depth-First Search (DFS) algorithm to navigate through the grid. The implementation relies on a helper dfs function that takes the coordinates (i, j) of the current cell and returns the count of fish caught starting from that cell.

Here is the approach broken down:

1. The dfs function initiates with the grid cell coordinates (i, j) and proceeds to capture all fish at this location. It sets the fish count at this cell to 0 to mark the cell as "fished out" and to prevent revisiting during the same DFS traversal.

2. We then iterate over the four possible directions (up, down, left, right) to move from the current cell to an adjacent one. This is done efficiently by using a loop and the pairwise utility, iterating over pairs of directional movements encoded as (dx, dy) deltas.

3. For each potential move to an adjacent cell (x, y), we check if the cell is within bounds of the grid, and if it is a water cell (grid[x][y] > 0). If it fits these criteria, we call the dfs function recursively for that cell.

4. The counts of fish from the current cell and from recursively applied DFS calls are summed up to get the total count of fish in this connected water region.

5. The outer loop of the Solution class iterates through all cells (i, j) in the grid. For each water cell identified (grid[i][j] > 0), it invokes the dfs function and captures the return value.

6. We maintain a variable ans to keep track of the maximum fish count seen so far. Every time we get a count back from a dfs call, we update ans with the maximum of its current value and the newly obtained count.

7. After the loop completes, we return the value of ans as the result, representing the maximum number of fish that can be caught starting from the best water cell.

The combination of recursive DFS and careful updates ensures that we thoroughly explore each connected water region, never double count, and always remember the "best" starting cell found in terms of fish count.

Mentioned in the Reference Solution Approach, the DFS method inherently works well for this problem because it naturally follows the constraints of the fisher's movement and fishing actions. Furthermore, by traversing and marking cells within the grid, we avoid the need for an auxiliary data structure to keep track of visited cells, thereby utilizing the grid for dual purposes—both as the map of the fishing area and as the record of visited water cells.

Here's the pseudocode that encapsulates this solution:

1function dfs(i, j):
2    cnt = grid[i][j]
3    grid[i][j] = 0  // Mark as visited (fished out)
4    for each direction (up, down, left, right) do:
5        x, y = new coordinates in direction
6        if (x, y) is in bounds and is water cell then:
7            cnt += dfs(x, y)
8    return cnt
9
10for each cell (i, j) in grid do:
11    if grid[i][j] > 0 then:
12        ans = max(ans, dfs(i, j))
13
14return ans

The final external for loop ensures that every water region is considered, while the recursive dfs functions guarantee a thorough exploration of each region.

Example Walkthrough

Let's take a 3x3 grid to illustrate the solution approach.

1grid = [
2  [2, 3, 1],
3  [0, 0, 4],
4  [7, 6, 0]
5]

In this grid, 0 represents land cells, and non-zero values like 2, 3, 1, etc., represent water cells with the corresponding number of fish in them.

Let's apply the DFS algorithm on the grid.

1. Starting at the top left corner, (0, 0) has 2 fish. We start here and set grid[0][0] to 0 which now looks like:

1grid = [
2  [0, 3, 1],
3  [0, 0, 4],
4  [7, 6, 0]
5]

2. From (0, 0), we look at adjacent cells up, down, left and right. Only two cells are adjacent and they are water cells: (0, 1) and (1, 2).

3. Next, we go to (0, 1), where there are 3 fish. After setting grid[0][1] to 0, the grid is:

1grid = [
2  [0, 0, 1],
3  [0, 0, 4],
4  [7, 6, 0]
5]

4. From (0, 1), we only have one water cell adjacent which is (0, 2), so we move there and add 1 fish to our count and mark the cell as visited:

1grid = [
2  [0, 0, 0],
3  [0, 0, 4],
4  [7, 6, 0]
5]

This completes the DFS for one water region originating from (0, 0). The total fish caught so far is 2+3+1 = 6 fish.

5. We then continue the external loop and come across the cell (1, 2) and start a new DFS because grid[1][2] > 0. This cell is isolated and only has 4 fish. After fishing, the grid updates as follows:

1grid = [
2  [0, 0, 0],
3  [0, 0, 0],
4  [7, 6, 0]
5]

6. Finally, we explore the cell (2, 0), triggering another DFS call. This region includes the cells (2, 0) and (2, 1) with a total of 7 + 6 = 13 fish.

1grid = [
2  [0, 0, 0],
3  [0, 0, 0],
4  [0, 0, 0]
5]

Following these steps, we have the maximum fish counts from each standalone water region:

• Starting at (0, 0) - we caught 6 fish.
• Starting at (1, 2) - we caught 4 fish.
• Starting at (2, 0) - we caught 13 fish.

Our answer ans is the maximum of these, which is 13 fish.

The procedure ensures that we never revisited any water cell and always accounted for the whole region before moving to the next. The final answer is the maximum fish caught across all regions, taking into account that only one region can be fully fished by starting at the optimal water cell.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the algorithm is O(m*n) because the dfs function is called for every cell in the grid at most once. Each cell is visited and then it's marked as 0 (zero) to avoid revisiting. Consequently, every cell (where m is the number of rows and n is the number of columns of the grid) is accessed in the worst case.

Space Complexity

The space complexity is O(m*n) in the worst-case scenario, which occurs when the grid is fully filled with non-zero values, leading to the deepest recursion of dfs potentially reaching m*n calls in the call stack before returning.

Learn more about how to find time and space complexity quickly using problem constraints.