Medium
LABMaximum Number of Fish in a Grid
Return the largest fish sum in any connected component of positive cells in the grid.
EXAMPLES
Example 1
Input
{
"grid": [
[
0,
2,
1,
0
],
[
4,
0,
0,
3
],
[
1,
0,
0,
4
],
[
0,
3,
2,
0
]
]
}
Output
7FUNCTION SHAPE
grid: intMatrix→intSOLUTION NOTE
Pretty standard dfs. We basically want the sum of values in each island, and return the max sum island.
Reveal reference solution +
pythonREFERENCE
def findMaxFish(self, grid: List[List[int]]) -> int:
m,n = len(grid), len(grid[0])
def dfs(i,j):
if not (0 <= i < m and 0 <= j < n) or grid[i][j] == 0: return 0
tmp = grid[i][j]
grid[i][j] = 0 # mark visited
return tmp + sum(dfs(i+x,j+y) for x,y in [(0,1),(1,0),(-1,0),(0,-1)])
return max(dfs(i,j) for i in range(m) for j in range(n))Time
O(m*n)Space
O(m*n)