# https://leetcode.com/problems/maximum-number-of-fish-in-a-grid

from typing import List

DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        r_size, c_size = len(grid), len(grid[0])
        visited = [[False] * c_size for _ in range(r_size)]
        max_fish = 0

        def dfs(r, c):
            if r < 0 or \
                r >= r_size or \
                c < 0 or \
                c >= c_size or \
                visited[r][c] or grid[r][c] == 0:
                return 0
            visited[r][c] = True
            fish_count = grid[r][c]
            for dr, dc in DIRS:
                fish_count += dfs(r + dr, c + dc)
            return fish_count

        for r in range(r_size):
            for c in range(c_size):
                if grid[r][c] > 0 and not visited[r][c]:
                    max_fish = max(max_fish, dfs(r, c))
        
        return max_fish