🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏| JAVA | C | C++ | PYTHON| JAVASCRIPT | DART 
IntuitionThe problem requires us to find the maximum number of fish that can be caught in a grid, where each cell can contain a certain number of fish. The goal
![image.png](https://assets.leetcode.com/users/images/79a16036-75f7-4794-9700-5d78373e6595_1738079214.2218225.png)

---

![1000072431.png](https://assets.leetcode.com/users/images/11ba933e-0e03-407a-a71d-410c1114e24d_1738079713.561122.png)

---

## Intuition
The problem requires us to find the maximum number of fish that can be caught in a grid, where each cell can contain a certain number of fish. The goal is to explore connected cells (up, down, left, right) starting from any cell that contains fish, and sum up the total number of fish in that connected component. My initial thought is to use depth-first search (DFS) to traverse the grid and keep track of the total fish caught from each starting cell.

## Approach
1. **Grid Traversal**:
   - Initialize variables to store the dimensions of the grid (`m` for rows and `n` for columns) and a variable (`maxFish`) to keep track of the maximum number of fish caught.
   - Define possible movement directions (up, right, down, left) in a list.

2. **Depth-First Search (DFS)**:
   - Implement a recursive DFS function that takes the current cell's coordinates and the grid as parameters.
   - In the DFS function:
     - Check if the current cell is out of bounds or has no fish (i.e., value is 0 or less). If so, return 0.
     - Capture the number of fish in the current cell and mark it as visited by setting its value to 0.
     - Recursively call DFS for all four possible directions from the current cell, summing up the total fish caught.

3. **Finding Maximum Fish**:
   - Iterate through each cell in the grid. If a cell contains fish (greater than 0), call the DFS function from that cell to calculate the total fish caught in that connected component.
   - Update `maxFish` with the maximum value found during these calls.

4. **Return Result**:
   - After checking all cells, return `maxFish`, which represents the maximum number of fish that can be caught from any connected component.

### Code Examples


```cpp []
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findMaxFish(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int maxFish = 0;
        vector<vector<int>> directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        
        function<int(int, int)> dfs = [&](int r, int c) {
            if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] <= 0) return 0;

            int fishCaught = grid[r][c];
            grid[r][c] = 0; // Mark as visited
            for (const auto& dir : directions) {
                fishCaught += dfs(r + dir[0], c + dir[1]);
            }

            return fishCaught;
        };

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) {
                    maxFish = max(maxFish, dfs(i, j));
                }
            }
        }

        return maxFish;
    }
};
```


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

        // Helper method for DFS
        int dfs(int r, int c) {
            if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] <= 0) return 0;

            int fishCaught = grid[r][c];
            grid[r][c] = 0; // Mark as visited
            for (int[] dir : directions) {
                fishCaught += dfs(r + dir[0], c + dir[1]);
            }

            return fishCaught;
        }

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

        return maxFish;
    }
}
```


```javascript []
class Solution {
    findMaxFish(grid) {
        const m = grid.length;
        const n = grid[0].length;
        let maxFish = 0;
        const directions = [[-1, 0], [0, 1], [1, 0], [0, -1]];

        const dfs = (r, c) => {
            if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] <= 0) return 0;

            let fishCaught = grid[r][c];
            grid[r][c] = 0; // Mark as visited
            for (const [dr, dc] of directions) {
                fishCaught += dfs(r + dr, c + dc);
            }

            return fishCaught;
        };

        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (grid[i][j] > 0) {
                    maxFish = Math.max(maxFish, dfs(i, j));
                }
            }
        }

        return maxFish;
    }
}
```


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

        def dfs(r: int, c: int) -> int:
            if r < 0 or c < 0 or r >= m or c >= n or grid[r][c] <= 0:
                return 0

            fish_caught = grid[r][c]
            grid[r][c] = 0 # Mark as visited
            for dr, dc in directions:
                fish_caught += dfs(r + dr, c + dc)

            return fish_caught

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

        return max_fish
```


```dart []
class Solution {
  int findMaxFish(List<List<int>> grid) {
    int m = grid.length;
    int n = grid[0].length;
    int maxFish = 0;
    List<List<int>> directions = [
      [-1, 0],
      [0, 1],
      [1, 0],
      [0, -1],
    ];

    int dfs(int r, int c) {
      if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] <= 0) return 0;

      int fishCaught = grid[r][c];
      grid[r][c] = 0; // Mark as visited
      for (int i = 0; i < directions.length; i++) {
          fishCaught += dfs(r + directions[i][0], c + directions[i][1]);
      }

      return fishCaught;
    }

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
          if (grid[i][j] > 0) {
              maxFish = max(maxFish, dfs(i,j));
          }
      }
    }

    return maxFish;
   }
}
```

## Complexity

- **Time complexity**: $$O(n \times m)$$ where $$n$$ is the number of rows and $$m$$ is the number of columns in `grid`. This accounts for visiting each cell at most once during DFS traversal.

- **Space complexity**: $$O(n \times m)$$ due to recursion stack space used by DFS. In the worst case where all cells are connected and need to be visited recursively.


---

![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style='width:250px'}
['Array', 'Depth-First Search', 'C', 'Matrix', 'C++', 'Java', 'Python3', 'JavaScript', 'Dart']