⚡Flashcard Drill➔
NeetCode #564LC-2658MediumGraphs
← Back to All Problems

#564 · #2658 · Maximum Number of Fish in a Grid(网格图中鱼的最大数目)

📌 Problem Statement & Constraints

You are given an m x n grid where 0 is water and a positive value is the number of fish in that water cell. A fisherman can start at any water cell and move to 4-directionally adjacent water cells. Return the maximum number of fish they can catch. Constraints: 1 <= m, n <= 10, 0 <= grid[i][j] <= 10.

💡 Core Algorithmic Approaches

  1. Each connected component of water cells is one fishing region; the catch is its total.
  2. So flood-fill every water component, summing the values.
  3. Mark cells as water (0) after visiting to avoid recounting.
  4. The answer is the maximum over all components.

💻 Benchmark Python3 Implementation

class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def dfs(r: int, c: int) -> int:
            if not (0 <= r < m and 0 <= c < n) or grid[r][c] == 0:
                return 0
            fish = grid[r][c]
            grid[r][c] = 0                 # mark as visited
            return (fish + dfs(r + 1, c) + dfs(r - 1, c)
                    + dfs(r, c + 1) + dfs(r, c - 1))

        return max((dfs(i, j) for i in range(m) for j in range(n)), default=0)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): each cell is visited at most once.
💾 Space Complexity
O(m * n) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting to mark visited: cells would be counted repeatedly.
  • Returning 0 for a grid with no water: the default=0 handles it.
  • Using a separate visited set: in-place zeroing is free.
  • Summing across components: each component is a separate fishing trip.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems