Maximum Number of Fish in a Grid

medium graph dfs bfs matrix

Problem

You are given a 2D grid where each cell is either land (value 0) or water. A water cell holds grid[r][c] fish, a positive number. A fisher may start at any water cell, catch all its fish, then repeatedly move to a 4-directionally adjacent water cell and catch its fish too. Return the largest total number of fish that can be caught starting from a single chosen cell, or 0 if the grid has no water.

Inputgrid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]

Output7

The water cells at (1,3)=3 and (2,3)=4 are connected, giving 3 + 4 = 7 fish, the best of any region.

grid (rows separated by ';', cells by ',')

def find_max_fish(grid):
    m, n = len(grid), len(grid[0])
    def dfs(r, c):
        if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0:
            return 0
        fish = grid[r][c]
        grid[r][c] = 0
        return fish + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)
    best = 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] > 0:
                best = max(best, dfs(r, c))
    return best

function findMaxFish(grid) {
  const m = grid.length, n = grid[0].length;
  function dfs(r, c) {
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] === 0) return 0;
    const fish = grid[r][c];
    grid[r][c] = 0;
    return fish + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1);
  }
  let best = 0;
  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++)
    if (grid[r][c] > 0) best = Math.max(best, dfs(r, c));
  return best;
}

class Solution {
    int[][] g; int m, n;
    public int findMaxFish(int[][] grid) {
        g = grid; m = grid.length; n = grid[0].length; int best = 0;
        for (int r = 0; r < m; r++) for (int c = 0; c < n; c++)
            if (g[r][c] > 0) best = Math.max(best, dfs(r, c));
        return best;
    }
    int dfs(int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n || g[r][c] == 0) return 0;
        int fish = g[r][c];
        g[r][c] = 0;
        return fish + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1);
    }
}

int m, n;
int dfs(vector<vector<int>>& g, int r, int c) {
    if (r < 0 || r >= m || c < 0 || c >= n || g[r][c] == 0) return 0;
    int fish = g[r][c];
    g[r][c] = 0;
    return fish + dfs(g, r+1, c) + dfs(g, r-1, c) + dfs(g, r, c+1) + dfs(g, r, c-1);
}
int findMaxFish(vector<vector<int>>& grid) {
    m = grid.size(); n = grid[0].size(); int best = 0;
    for (int r = 0; r < m; r++) for (int c = 0; c < n; c++)
        if (grid[r][c] > 0) best = max(best, dfs(grid, r, c));
    return best;
}

Explanation

Think of the water cells as a graph: two water cells are connected if they sit next to each other up, down, left, or right. A fisher who starts somewhere can reach exactly one connected region of water, and will scoop up every fish in it. So the answer is the total fish in the heaviest region.

To measure a region we use flood fill with DFS. The function dfs(r, c) returns the total fish reachable from that cell. It returns 0 when the cell is off the grid or is land (value 0); otherwise it remembers the fish in the current cell, zeroes the cell out to mark it visited, and adds the fish from its four neighbors.

Setting the cell to 0 in place is the key trick. It both marks the cell as used and makes it look like land, so we never count the same water twice and need no separate visited grid.

The outer loops walk every cell. Whenever they meet a water cell that has not been drained yet, they launch a fresh DFS for a new region and compare its total against the running best.

Example: grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]. The region {(0,1)=2, (0,2)=1} gives 3, the cell (1,0)=4 gives 4, the region {(1,3)=3, (2,3)=4} gives 7, the cell (2,0)=1 gives 1, and {(3,1)=3, (3,2)=2} gives 5. The largest is 7.

Time: O(m·n) Space: O(m·n)