BFS/DFS 100% beats Two Detailed Explanation
IntuitionThe problem involves finding the maximum "fish" that can be collected from connected components in a grid. Each cell in the grid represents the number
# Intuition
The problem involves finding the maximum "fish" that can be collected from connected components in a grid. Each cell in the grid represents the number of fish, and cells are considered connected if they are adjacent (horizontally or vertically). The task can be broken into identifying connected components and calculating the sum of fish in each.

The intuition here is to use a traversal method (like BFS or DFS) to explore connected components starting from every cell containing fish. During the traversal, we keep track of the sum of fish in the current connected component and update the maximum.

---

# Approach
1. **Initialization**:
   - Iterate through each cell in the grid.
   - If the cell contains fish (value > 0), start a traversal (BFS) to explore the connected component.

2. **Traversal (BFS)**:
   - Use a queue to manage the cells to explore.
   - Add the starting cell to the queue and mark it as visited by setting its value to `0`.
   - For each cell, add its fish value to the current component's sum and enqueue its unvisited neighbors with fish.

3. **Update the Maximum**:
   - After completing the traversal of a connected component, compare its total fish with the current maximum and update accordingly.

4. **Optimization**:
   - Instead of using a separate `Visit` matrix, mark cells as visited by setting their value to `0`, reducing memory overhead.

---

# Complexity
- **Time Complexity**:  
  $$O(m \times n)$$  
  - Each cell is processed once, either as part of the BFS traversal or skipped because it's water (`0`).

- **Space Complexity**:  
  $$O(m \times n)$$  
  - In the worst case, the queue can hold all the cells in a connected component.

![Screenshot 2025-01-28 065006.png](https://assets.leetcode.com/users/images/00991356-f22d-4c36-828a-1416a30e8320_1738027463.5096087.png)
![9c6f9412-c860-47d6-9a2e-7fcf37ff3321_1686334926.180891.png](https://assets.leetcode.com/users/images/dbe2a095-628a-4078-b40a-0452f3f4f62f_1738027479.6325665.png)



---
# Code
```CPP_BFS []
class Solution {
public:
    int findMaxFish(vector<vector<int>>& grid) {
        int Max = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] > 0) {
                    int C = 0;
                    queue<pair<int, int>> T;
                    T.push({i, j});
                    while (!T.empty()) {
                        auto [x, y] = T.front();
                        T.pop();
                        if (grid[x][y] > 0) {
                            C += grid[x][y];
                            grid[x][y] = 0; // Mark as visited
                            if (x > 0 && grid[x - 1][y] > 0) T.push({x - 1, y});
                            if (x + 1 < grid.size() && grid[x + 1][y] > 0) T.push({x + 1, y});
                            if (y > 0 && grid[x][y - 1] > 0) T.push({x, y - 1});
                            if (y + 1 < grid[0].size() && grid[x][y + 1] > 0) T.push({x, y + 1});
                        }
                    }
                    Max = max(Max, C);
                }
            }
        }
        return Max;
    }
};
```
``` CPP_DFS []
class Solution {
public:
    int exploreRegion(int row, int col, vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        if (row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] == 0) return 0;
        int currentFish = grid[row][col];
        grid[row][col] = 0;
        currentFish += exploreRegion(row + 1, col, grid);
        currentFish += exploreRegion(row - 1, col, grid);
        currentFish += exploreRegion(row, col + 1, grid);
        currentFish += exploreRegion(row, col - 1, grid);
        return currentFish;
    }

    int findMaximumFish(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size(), maxFish = 0;
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (grid[row][col] != 0) {
                    maxFish = max(maxFish, exploreRegion(row, col, grid));
                }
            }
        }
        return maxFish;
    }
};
```
['Depth-First Search', 'Breadth-First Search', 'Matrix', 'C++']