---
# System prepended metadata

title: 2658. Maximum Number of Fish in a Grid
tags: [Leetcode, DFS, Medium]

---

Link: https://leetcode.com/problems/maximum-number-of-fish-in-a-grid/description/
## 思路
Note in python, if you define 2d array using ```arr = [[0]*cols]*rows```, each row will be referencing the same column. This means, even if we update only one element of the array, it will update same column in our array.
So you should define 2d array like this: ```visited = [[0 for i in range(c)] for j in range(r)]```
一开始的做法是所有之前遍历过的地方都不再遍历了 code在下面
但是这样如果grid=[[10,5],[8,0]] 就行不通
## Code
```python=
class Solution:
    def findMaxFish(self, grid: List[List[int]]):
        r, c = len(grid), len(grid[0])
        dirs = [[0,1], [0,-1], [1,0], [-1,0]]
        
        def dfs(grid: List[List[int]], x: int, y: int):
            tmp = grid.copy()
            if x<0 or y<0 or x>=r or y>=c or tmp[x][y]==0:
                return 0
            res = grid[x][y]
            tmp[x][y] = 0
            for dir in dirs:
                res += dfs(tmp, x+dir[0], y+dir[1])
            return res

        ans = 0
        for i in range(r):
            for j in range(c):
                ans = max(ans, dfs(grid, i, j))
        return ans
```
### 一开始的code
```python=
class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        r, c = len(grid), len(grid[0])
        visited = [[False for i in range(c)] for j in range(r)]
        ans = 0
        dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        
        def dfs(i, j):
            maxFish = grid[i][j]
            visited[i][j] = True
            for dir in dirs:
                newi = i+dir[0]
                newj = j+dir[1]
                if newi>=0 and newi<r and newj>=0 and newj<c and grid[newi][newj]!=0 and not visited[newi][newj]:
                    visited[newi][newj] = True
                    maxFish = max(maxFish, grid[i][j]+dfs(newi, newj))
            return maxFish
        
        for i in range(r):
            for j in range(c):
                if not visited[i][j] and grid[i][j]!=0:
                    curr = dfs(i, j)
                    ans = max(ans, curr)

        return ans
```