aboutsummaryrefslogtreecommitdiff
path: root/max_num_fish_grid.py
blob: 05492d3d888f7364be86808ccb2e038de07e0407 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# 2658. Maximum Number of Fish in a Grid

"""
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'. afisher can start at any water cell
and can do the following operations any number of times: catch all the fish
at the current cell, 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 cells exist.
"""


class Solution(object):
    def dfs(self, grid, r, c, n, m):
        dir = [0, 1, 0, -1, 0]
        cnt = grid[r][c]
        grid[r][c] = 0
        for i in range(4):
            nr = r + dir[i]
            nc = c + dir[i + 1]
            if nr >= 0 and nr < n and nc >= 0 and nc < m and grid[nr][nc] > 0:
                cnt += self.dfs(grid, nr, nc, n, m)
        return cnt

    def findMaxFish(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        n, m, ans = len(grid), len(grid[0]), 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] > 0:
                    ans = max(ans, self.dfs(grid, i, j, n, m))
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(
        obj.findMaxFish(grid=[[0, 2, 1, 0], [4, 0, 0, 3], [1, 0, 0, 4], [0, 3, 2, 0]])
    )
    print(
        obj.findMaxFish(grid=[[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 1]])
    )