aboutsummaryrefslogtreecommitdiff
path: root/max_num_fish_grid.py
diff options
context:
space:
mode:
Diffstat (limited to 'max_num_fish_grid.py')
-rw-r--r--max_num_fish_grid.py46
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]])
+ )