Home Backend Development PHP Tutorial Maximum Number of Fish in a Grid

Maximum Number of Fish in a Grid

Jan 28, 2025 pm 10:03 PM

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:

Maximum Number of Fish in a Grid

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

Maximum Number of Fish in a Grid2

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

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

<?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

?>

Copy after login

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:

1

2

3

4

5

6

$grid = [

    [0, 2, 1, 0],

    [4, 0, 0, 3],

    [1, 0, 0, 4],

    [0, 3, 2, 0]

];

Copy after login

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:

  • LinkedIn
  • GitHub

The above is the detailed content of Maximum Number of Fish in a Grid. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Explain JSON Web Tokens (JWT) and their use case in PHP APIs. Explain JSON Web Tokens (JWT) and their use case in PHP APIs. Apr 05, 2025 am 12:04 AM

JWT is an open standard based on JSON, used to securely transmit information between parties, mainly for identity authentication and information exchange. 1. JWT consists of three parts: Header, Payload and Signature. 2. The working principle of JWT includes three steps: generating JWT, verifying JWT and parsing Payload. 3. When using JWT for authentication in PHP, JWT can be generated and verified, and user role and permission information can be included in advanced usage. 4. Common errors include signature verification failure, token expiration, and payload oversized. Debugging skills include using debugging tools and logging. 5. Performance optimization and best practices include using appropriate signature algorithms, setting validity periods reasonably,

How does session hijacking work and how can you mitigate it in PHP? How does session hijacking work and how can you mitigate it in PHP? Apr 06, 2025 am 12:02 AM

Session hijacking can be achieved through the following steps: 1. Obtain the session ID, 2. Use the session ID, 3. Keep the session active. The methods to prevent session hijacking in PHP include: 1. Use the session_regenerate_id() function to regenerate the session ID, 2. Store session data through the database, 3. Ensure that all session data is transmitted through HTTPS.

What are Enumerations (Enums) in PHP 8.1? What are Enumerations (Enums) in PHP 8.1? Apr 03, 2025 am 12:05 AM

The enumeration function in PHP8.1 enhances the clarity and type safety of the code by defining named constants. 1) Enumerations can be integers, strings or objects, improving code readability and type safety. 2) Enumeration is based on class and supports object-oriented features such as traversal and reflection. 3) Enumeration can be used for comparison and assignment to ensure type safety. 4) Enumeration supports adding methods to implement complex logic. 5) Strict type checking and error handling can avoid common errors. 6) Enumeration reduces magic value and improves maintainability, but pay attention to performance optimization.

Describe the SOLID principles and how they apply to PHP development. Describe the SOLID principles and how they apply to PHP development. Apr 03, 2025 am 12:04 AM

The application of SOLID principle in PHP development includes: 1. Single responsibility principle (SRP): Each class is responsible for only one function. 2. Open and close principle (OCP): Changes are achieved through extension rather than modification. 3. Lisch's Substitution Principle (LSP): Subclasses can replace base classes without affecting program accuracy. 4. Interface isolation principle (ISP): Use fine-grained interfaces to avoid dependencies and unused methods. 5. Dependency inversion principle (DIP): High and low-level modules rely on abstraction and are implemented through dependency injection.

Explain late static binding in PHP (static::). Explain late static binding in PHP (static::). Apr 03, 2025 am 12:04 AM

Static binding (static::) implements late static binding (LSB) in PHP, allowing calling classes to be referenced in static contexts rather than defining classes. 1) The parsing process is performed at runtime, 2) Look up the call class in the inheritance relationship, 3) It may bring performance overhead.

What is REST API design principles? What is REST API design principles? Apr 04, 2025 am 12:01 AM

RESTAPI design principles include resource definition, URI design, HTTP method usage, status code usage, version control, and HATEOAS. 1. Resources should be represented by nouns and maintained at a hierarchy. 2. HTTP methods should conform to their semantics, such as GET is used to obtain resources. 3. The status code should be used correctly, such as 404 means that the resource does not exist. 4. Version control can be implemented through URI or header. 5. HATEOAS boots client operations through links in response.

How do you handle exceptions effectively in PHP (try, catch, finally, throw)? How do you handle exceptions effectively in PHP (try, catch, finally, throw)? Apr 05, 2025 am 12:03 AM

In PHP, exception handling is achieved through the try, catch, finally, and throw keywords. 1) The try block surrounds the code that may throw exceptions; 2) The catch block handles exceptions; 3) Finally block ensures that the code is always executed; 4) throw is used to manually throw exceptions. These mechanisms help improve the robustness and maintainability of your code.

What are anonymous classes in PHP and when might you use them? What are anonymous classes in PHP and when might you use them? Apr 04, 2025 am 12:02 AM

The main function of anonymous classes in PHP is to create one-time objects. 1. Anonymous classes allow classes without names to be directly defined in the code, which is suitable for temporary requirements. 2. They can inherit classes or implement interfaces to increase flexibility. 3. Pay attention to performance and code readability when using it, and avoid repeatedly defining the same anonymous classes.

See all articles