diff options
Diffstat (limited to 'max_num_fish_grid.py')
-rw-r--r-- | max_num_fish_grid.py | 46 |
1 files changed, 46 insertions, 0 deletions
diff --git a/max_num_fish_grid.py b/max_num_fish_grid.py new file mode 100644 index 0000000..05492d3 --- /dev/null +++ b/max_num_fish_grid.py @@ -0,0 +1,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]]) + ) |