2658. Maximum Number of Fish in a Grid

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/maximum-number-of-fish-in-a-grid
• topics: 2D Array, DFS

Description

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.

Idea

• DFS

Code

class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        N, M = len(grid), len(grid[0])
        directions = [[0,1], [0,-1], [1,0], [-1,0]]
 
        def dfs(i: int, j: int): 
            nonlocal grid
            grid[i][j], total = 0, grid[i][j]
            for dx, dy in directions:
                if 0 <= (x:=i+dx) < N and 0 <= (y:=j+dy) < M and grid[x][y]: 
                    total += dfs(x, y)
            return total
 
        return max((dfs(i, j) for i in range(N) 
            for j in range(M) if grid[i][j]), default=0)