DEV Community

Cover image for 2658. Maximum Number of Fish in a Grid
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

2658. Maximum Number of Fish in a Grid

2658. Maximum Number of Fish in a Grid

Difficulty: Medium

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:

example

  • 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:

example2

  • 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.

Solution:

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) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * 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) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// 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
?>
Enter fullscreen mode Exit fullscreen mode

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]
];
Enter fullscreen mode Exit fullscreen mode

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.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

Image of AssemblyAI tool

Transforming Interviews into Publishable Stories with AssemblyAI

Insightview is a modern web application that streamlines the interview workflow for journalists. By leveraging AssemblyAI's LeMUR and Universal-2 technology, it transforms raw interview recordings into structured, actionable content, dramatically reducing the time from recording to publication.

Key Features:
🎥 Audio/video file upload with real-time preview
🗣️ Advanced transcription with speaker identification
⭐ Automatic highlight extraction of key moments
✍️ AI-powered article draft generation
📤 Export interview's subtitles in VTT format

Read full post

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay