leetcodedaybyday - Beats 84.06% with C++ and Beats 73.41% with Python3
IntuitionTo solve the problem, we can leverage a Depth-First Search (DFS) approach. The idea is to explore all connected cells in the grid that contain non-zero
# Intuition
To solve the problem, we can leverage a Depth-First Search (DFS) approach. The idea is to explore all connected cells in the grid that contain non-zero values, as they represent the regions containing fish. By performing DFS for each cell in the grid, we can calculate the total number of fish in connected components and track the maximum fish count.

# Approach
1. **DFS Traversal**:
   - Use a helper function `DFS` that takes the current cell and recursively explores all adjacent cells in the four cardinal directions (up, down, left, right).
   - Accumulate the fish count for the connected component and mark the cell as visited by setting its value to `0`.

2. **Iterate Over All Cells**:
   - For each cell in the grid, check if it contains a positive value (indicating fish).
   - If so, call the `DFS` function and update the maximum fish count based on the result.

3. **Edge Cases**:
   - Handle cases where the grid is empty or has only one row/column.
   - Ensure boundary conditions are respected during DFS traversal.


# Complexity
- **Time Complexity**:  
  O(r * c), where r is the number of rows and c is the number of columns.  
  Each cell is visited once during the DFS traversal.

- **Space Complexity**:  
  O(r * c) in the worst case due to the recursive stack during DFS, if the grid contains a single connected component.

# Code
```cpp []
class Solution {
public:
    const int d[5] = {0, 1, 0, -1, 0};
    int r, c;

    int DFS(int i, int j, vector<vector<int>>& grid){
        int fish = grid[i][j];
        grid[i][j] = 0;
        for (int a = 0; a < 4; a++){
            int row = i + d[a];
            int col = j + d[a + 1];
            if (row < 0 || row >= r || col < 0 || col >= c || grid[row][col] == 0){
                continue;
            }
            fish += DFS(row, col, grid);
        }
        return fish;
    }

    int findMaxFish(vector<vector<int>>& grid) {
        r = grid.size();
        c = grid[0].size();
        int ans = 0;
        for (int i = 0; i < r; i++){
            for (int j = 0; j < c; j++){
                if (grid[i][j] > 0){
                    ans = max(ans, DFS(i, j, grid));
                }
            }
        }
        return ans;
    }
};
```
```python3 []
class Solution:
    def __init__(self):
        self.d = [0, 1, 0, -1, 0]
        self.r = 0
        self.c = 0

    def DFS(self, i, j, grid):
        fish = grid[i][j]
        grid[i][j] = 0
        for a in range(4):
            row = i + self.d[a]
            col = j + self.d[a + 1]
            if row < 0 or row >= self.r or col < 0 or col >= self.c or grid[row][col] == 0:
                continue
            fish += self.DFS(row, col, grid)
        return fish

    def findMaxFish(self, grid: List[List[int]]) -> int:
        self.r = len(grid)
        self.c = len(grid[0])
        ans = 0
        for i in range(self.r):
            for j in range(self.c):
                if grid[i][j] > 0:
                    ans = max(ans, self.DFS(i, j, grid))

        return ans


```

['Depth-First Search', 'Matrix', 'C++', 'Python3']