Maximum Number of Fish in a Grid.py

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

 
 '''



class Solution:

    def dfs(self,grid,i,j,n,m):
        f = grid[i][j]
        grid[i][j] = 0 #important!
        for dr,dc in (1,0), (-1,0), (0,-1), (0,1):
            r = i + dr
            c = j + dc
            if 0 <= r < m and 0 <= c < n and grid[r][c]>0 :#aka water cell and within limits
                f+= self.dfs(grid,r,c,n,m)
        return f

    def findMaxFish(self, grid: List[List[int]]) -> int:

        ans = 0

        m = len(grid)
        n = len(grid[0])

        for i in range(m):
            for j in range(n):

                if grid[i][j] >0:
                    #dfs
                    ans = max(ans, self.dfs(grid,i,j,n,m) )        
        return ans