2658. Maximum Number of Fish in a Grid

[mah-shamim]

Topics: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix

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

Hint:

1. Run DFS from each non-zero cell.
2. Each time you pick a cell to start from, add up the number of fish contained in the cells you visit.

[mah-shamim]

The problem is to find the maximum number of fish that a fisher can catch by starting at any water cell in a grid. The fisher can catch fish at the current cell and move to any adjacent water cell (up, down, left, or right) repeatedly.

Key Points:

1. The grid contains cells that are either land (value 0) or water (value > 0).
2. The fisher can only move to adjacent water cells.
3. The objective is to find the maximum number of fish collectable, starting from the best possible water cell.

Approach:

1. Use Depth-First Search (DFS) to explore all possible paths starting from each water cell.
2. For each unvisited water cell, run a DFS to calculate the total fish in the connected component.
3. Track the maximum fish collected from any connected component.

Plan:

1. Initialize a 2D visited array to track whether a cell has been explored.
2. Iterate through each cell in the grid.
3. If the cell contains water and is not visited:
   • Run a DFS starting from that cell.
   • Accumulate the total fish in the connected water cells.
   • Update the maximum fish collected so far.
4. Return the maximum fish count after exploring all cells.

Let's implement this solution in PHP: 2658. Maximum Number of Fish in a Grid

<?php
/**
 * @param Integer[][] $grid
 * @return Integer
 */
function findMaxFish($grid) {
    $rows = count($grid);
    $cols = count($grid[0]);
    $visited = array_fill(0, $rows, array_fill(0, $cols, false));

    $directions = [
        [-1, 0], // up
        [1, 0],  // down
        [0, -1], // left
        [0, 1]   // right
    ];

    $maxFish = 0;

    for ($i = 0; $i < $rows; $i++) {
        for ($j = 0; $j < $cols; $j++) {
            if ($grid[$i][$j] > 0 && !$visited[$i][$j]) {
                $maxFish = max($maxFish, dfs($i, $j, $grid, $visited, $rows, $cols, $directions));
            }
        }
    }

    return $maxFish;
}

/**
 * Helper function for DFS
 * @param $r
 * @param $c
 * @param $grid
 * @param $visited
 * @param $rows
 * @param $cols
 * @param $directions
 * @return array|bool|int|int[]|mixed|null
 */
function dfs($r, $c, &$grid, &$visited, $rows, $cols, $directions) {
    if ($r < 0 || $c < 0 || $r >= $rows || $c >= $cols || $grid[$r][$c] == 0 || $visited[$r][$c]) {
        return 0;
    }

    $visited[$r][$c] = true;
    $fishCount = $grid[$r][$c];

    foreach ($directions as $dir) {
        $fishCount += dfs($r + $dir[0], $c + $dir[1], $grid, $visited, $rows, $cols, $directions);
    }

    return $fishCount;
}

// Example 1
grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]];
echo getMaxFish($grid); // Output: 7

// Example 2
$grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]];
echo getMaxFish($grid); // Output: 1
?>

Explanation:

DFS Implementation:

• For each water cell (r, c), recursively explore its neighbors if they are:
  • Inside the grid boundaries.
  • Unvisited.
  • Water cells (value > 0).
• Accumulate the fish count during the recursion.

Steps:

1. Start from a water cell and mark it as visited.
2. Recursively visit its valid neighbors, adding up the fish count.
3. Return the total fish count for the connected component.

Example Walkthrough:

Example Input:

$grid = [
    [0, 2, 1, 0],
    [4, 0, 0, 3],
    [1, 0, 0, 4],
    [0, 3, 2, 0]
];

Execution:

1. Start at (1, 3) (value = 3). Run DFS:
   • (1, 3) → (2, 3) (value = 4).
   • Total fish = 3 + 4 = 7.
2. Explore other water cells, but no connected component has a higher total fish count.
3. Output: 7.

Time Complexity:

• DFS Traversal: Each cell is visited once → O(m × n).
• Overall Complexity: O(m × n), where m and n are grid dimensions.

Output for Examples:

• Example 1: 7
• Example 2: 1

The solution efficiently uses DFS to explore connected components of water cells and calculates the maximum fish catchable by a fisher starting from any water cell. This approach ensures optimal exploration and works well for the given constraints.

[kovatz]

Thanks for solving the problem of "Maximum Number of Fish in a Grid"

[mah-shamim]

Thanks