Beats 100% | DFS | Matrix | Solution for LeetCode#2658
IntuitionThe problem seems to be about finding the maximum number of fish that can be caught from a connected area in a 2D grid. The intuition is to use a depth
![image.png](https://assets.leetcode.com/users/images/1c9f7cef-498c-4d51-b8e4-d2e9d56cb201_1738033504.5080497.png)

# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem seems to be about finding the maximum number of fish that can be caught from a connected area in a 2D grid. The intuition is to use a depth-first search (DFS) to explore connected cells with fish and sum up the total fish in each connected component.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Iterate through each cell in the grid.
2. If a cell contains fish (value > 0), start a DFS from that cell.
3. In the DFS:
	- Mark the current cell as visited.
	- Add the fish in the current cell to the total.
	- Recursively explore the four adjacent cells (up, down, left, right).
	- Return the total fish caught in this connected component.
4. Keep track of the maximum fish caught among all connected components.

# Complexity
- Time complexity: O(m * n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(m * n)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code Option-01
![image.png](https://assets.leetcode.com/users/images/e63e7f8b-d979-4f65-8dac-26d3fe77abcf_1738027037.2255647.png)

```java []
class Solution {
    int[][] directions={ {0,1},{0,-1}, {1,0},{-1,0} };
    boolean[][] visited;
    
    public int findMaxFish(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int maxFish=0;       

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j]==0) continue;
                
                visited=new boolean[m][n];
                               
                maxFish=Math.max(maxFish, dfs(grid, i, j, m, n));
            }
        }

        return maxFish;
    }

    int dfs(int[][] grid, int i, int j, int m, int n){
        visited[i][j]=true;
        int fish=0;
        
        if(grid[i][j]==0) return fish;

        fish+=grid[i][j];
        for(int[] dir:directions){
            int nr=i+dir[0];
            int nc=j+dir[1];
            if(nr>=0 && nr<m && nc>=0 && nc<n){
                if(!visited[nr][nc]){                           
                    fish+=dfs(grid, nr, nc, m, n);
                }
            }
        } 

        return fish;
    }

}
```

# Code Option-02
![image.png](https://assets.leetcode.com/users/images/81758324-7f61-4253-91e3-dccfe8450201_1738033500.039256.png)

```java []
class Solution {
    
    public int findMaxFish(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int maxFish=0;       

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j]==0) continue;    

                maxFish=Math.max(maxFish, dfs(grid, i, j, m, n));
            }
        }

        return maxFish;
    }

    int dfs(int[][] grid, int i, int j, int m, int n){        
        int fish=0;
        
        if( i<0 || i>=m || j<0 || j>=n || grid[i][j]==0) return fish;   
             
        fish+=grid[i][j];
        
        grid[i][j]=0; //Visited

                                           
        fish+=dfs(grid, i, j+1, m, n);
        fish+=dfs(grid, i, j-1, m, n);
        fish+=dfs(grid, i+1, j, m, n);
        fish+=dfs(grid, i-1, j, m, n);
        

        return fish;
    }

}
```

# Code Option-03
![image.png](https://assets.leetcode.com/users/images/7a5ae6fa-62ab-4739-92bb-ac4e7d590958_1738028404.817257.png)

```java []
class Solution {
    int[][] directions={ {0,1},{0,-1}, {1,0},{-1,0} };
    
    public int findMaxFish(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int maxFish=0;       

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j]==0) continue;    

                maxFish=Math.max(maxFish, dfs(grid, i, j, m, n));
            }
        }

        return maxFish;
    }

    int dfs(int[][] grid, int i, int j, int m, int n){        
        int fish=0;
        
        if(grid[i][j]==0) return fish;   
             
        fish+=grid[i][j];
        
        grid[i][j]=-1; //Visited

        for(int[] dir:directions){
            int nr=i+dir[0];
            int nc=j+dir[1];
            if(nr>=0 && nr<m && nc>=0 && nc<n){
                if(grid[nr][nc]>0){                           
                    fish+=dfs(grid, nr, nc, m, n);
                }
            }
        } 

        return fish;
    }

}
```
```python []
class Solution(object):
    def findMaxFish(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        directions = [[0,1], [0,-1], [1,0], [-1,0]]
        m = len(grid)
        n = len(grid[0])
        maxFish = 0

        def dfs(i, j, m, n):
            fish = 0
            
            if grid[i][j] == 0:
                return fish
            
            fish += grid[i][j]
            grid[i][j] = -1  # Visited

            for dir in directions:
                nr = i + dir[0]
                nc = j + dir[1]
                if 0 <= nr < m and 0 <= nc < n:
                    if grid[nr][nc] > 0:
                        fish += dfs(nr, nc, m, n)
            
            return fish

        for i in xrange(m):
            for j in xrange(n):
                if grid[i][j] == 0:
                    continue
                maxFish = max(maxFish, dfs(i, j, m, n))

        return maxFish
```
```python [Python3]
class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        directions = [[0,1], [0,-1], [1,0], [-1,0]]
        m = len(grid)
        n = len(grid[0])
        maxFish = 0

        def dfs(i: int, j: int, m: int, n: int) -> int:
            fish = 0
            
            if grid[i][j] == 0:
                return fish
            
            fish += grid[i][j]
            grid[i][j] = -1  # Visited

            for dir in directions:
                nr = i + dir[0]
                nc = j + dir[1]
                if 0 <= nr < m and 0 <= nc < n:
                    if grid[nr][nc] > 0:
                        fish += dfs(nr, nc, m, n)
            
            return fish

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    continue
                maxFish = max(maxFish, dfs(i, j, m, n))

        return maxFish
```
```cpp []
class Solution {
public:
    vector<vector<int>> directions = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    
    int findMaxFish(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int maxFish = 0;       

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 0) continue;    

                maxFish = max(maxFish, dfs(grid, i, j, m, n));
            }
        }

        return maxFish;
    }

private:
    int dfs(vector<vector<int>>& grid, int i, int j, int m, int n){        
        int fish = 0;
        
        if(grid[i][j] == 0) return fish;   
             
        fish += grid[i][j];
        
        grid[i][j] = -1; // Visited

        for(const auto& dir : directions){
            int nr = i + dir[0];
            int nc = j + dir[1];
            if(nr >= 0 && nr < m && nc >= 0 && nc < n){
                if(grid[nr][nc] > 0){                           
                    fish += dfs(grid, nr, nc, m, n);
                }
            }
        } 

        return fish;
    }
};

```
['Depth-First Search', 'Python', 'C++', 'Java', 'Python3']