DFS solution || C++ || Python
IntuitionThe problem involves identifying connected components in a grid where each cell represents either a body of water (0) or a cluster of fish (non-zero po
# Intuition
The problem involves identifying connected components in a grid where each cell represents either a body of water (0) or a cluster of fish (non-zero positive integers). The goal is to calculate the maximum number of fish in any connected cluster, where connectivity is defined as adjacency in the 4 cardinal directions (up, down, left, right). This can be solved using Depth First Search (DFS) to traverse and count the fish in each cluster.

# Approach
1. **Initialization**:  
   Create a `visited` matrix of the same size as the grid to track the cells that have been processed.

2. **DFS Traversal**:  
   - Use DFS to explore all connected cells starting from an unvisited cell containing fish.  
   - For each cell visited during the DFS, add its fish count to a running total.  
   - Mark the cell as visited to prevent revisiting it.

3. **Iterate Through the Grid**:  
   - Loop through all cells in the grid.
   - If a cell contains fish (value > 0) and hasn't been visited, initiate a DFS from that cell and calculate the total fish count for the connected component.

4. **Track the Maximum**:  
   Keep track of the maximum fish count found during the traversal.

5. **Return the Result**:  
   After processing the entire grid, return the maximum fish count.

# Complexity
- **Time Complexity**: $$O(m \times n)$$  
  - Each cell in the grid is visited exactly once during the DFS traversal.  
  - For a grid with dimensions $$m \times n$$, the total time complexity is proportional to the number of cells.

- **Space Complexity**: $$O(m \times n)$$  
  - The `visited` matrix requires $$O(m \times n)$$ space.  
  - The recursion stack for the DFS can hold up to $$O(m \times n)$$ calls in the worst case (e.g., a fully connected grid with fish).

# Why This Works
1. **DFS Correctly Identifies Connected Components**:  
   The DFS explores all adjacent cells recursively, ensuring that each cluster of connected fish is fully traversed.

2. **Marking Cells as Visited Prevents Reprocessing**:  
   This avoids redundant calculations and ensures that each cell is processed exactly once.

3. **Iterating Over the Grid Ensures Full Coverage**:  
   By starting a new DFS for every unvisited cell with fish, all clusters are discovered.


# Code
```cpp []
class Solution {
public:
    int dfs(vector<vector<int>>& grid, vector<vector<int>>& visited, int row, int col) {
        int n = grid.size();
        int m = grid[0].size();

        if (row < 0 || col < 0 || row >= n || col >= m || grid[row][col] == 0 || visited[row][col] == 1) {
            return 0;
        }

        visited[row][col] = 1;

        int total_fishes = grid[row][col];

        total_fishes += dfs(grid, visited, row + 1, col);  // Down
        total_fishes += dfs(grid, visited, row - 1, col);  // Up
        total_fishes += dfs(grid, visited, row, col + 1);  // Right
        total_fishes += dfs(grid, visited, row, col - 1);  // Left

        return total_fishes;
    }

    int findMaxFish(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int max_fish = 0;

        vector<vector<int>> visited(n, vector<int>(m, 0));

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

        return max_fish;
    }
};
```
``` python []
class Solution:
    def dfs(self, grid, visited, row, col):
        n = len(grid)
        m = len(grid[0])

        # Boundary checks and already visited or water cell checks
        if row < 0 or col < 0 or row >= n or col >= m or grid[row][col] == 0 or visited[row][col]:
            return 0

        # Mark the cell as visited
        visited[row][col] = True

        # Collect fish from the current cell
        total_fishes = grid[row][col]

        # Perform DFS in all 4 directions
        total_fishes += self.dfs(grid, visited, row + 1, col)  # Down
        total_fishes += self.dfs(grid, visited, row - 1, col)  # Up
        total_fishes += self.dfs(grid, visited, row, col + 1)  # Right
        total_fishes += self.dfs(grid, visited, row, col - 1)  # Left

        return total_fishes

    def findMaxFish(self, grid):
        n = len(grid)
        m = len(grid[0])
        max_fish = 0

        # Visited matrix to track which cells have been processed
        visited = [[False for _ in range(m)] for _ in range(n)]

        for i in range(n):
            for j in range(m):
                # Start a DFS for each unvisited cell containing fish
                if grid[i][j] > 0 and not visited[i][j]:
                    max_fish = max(max_fish, self.dfs(grid, visited, i, j))

        return max_fish
```
['Array', 'Depth-First Search', 'Matrix', 'C++', 'Python3']