BFS & DFS Approach Python Solution
DFS Solution# IntuitionThe problem involves finding the maximum number of fish that can be collected in a grid by moving in 4 possible directions (up, down, lef
### DFS Solution

---

#### **# Intuition**
The problem involves finding the maximum number of fish that can be collected in a grid by moving in 4 possible directions (up, down, left, right). Since connected components of non-zero cells represent a valid path to collect fish, the goal is to explore all such components and track the maximum sum. A **depth-first search (DFS)** is suitable because it allows us to recursively explore each connected component efficiently.

---

#### **# Approach**
1. **Initialize Variables**:
   - Create a DFS function that will explore all connected non-zero cells starting from a given cell.
   - Track visited cells by marking them as \(0\) in the grid after processing.

2. **DFS Traversal**:
   - Recursively visit each valid neighbor (within bounds and non-zero).
   - Accumulate the fish count from the current cell and neighbors.

3. **Iterate Over the Grid**:
   - For each cell in the grid, if it is non-zero, invoke the DFS function to calculate the total fish in that connected component.
   - Update the maximum fish count.

4. **Return the Result**:
   - After visiting all cells, return the maximum fish count.

---

# Code
```python3 []
class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        def dfs(x,y):
            maxi = 0
            if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] == 0:
                return maxi 

            maxi += grid[x][y]
            grid[x][y] = 0
            return dfs(x+1,y) + dfs(x-1,y) + dfs(x,y+1) + dfs(x,y-1) + maxi

        maximum = 0
        for x in range(len(grid)):
            for y in range(len(grid[0])):
                if grid[x][y] != 0:
                    maximum = max(maximum, dfs(x,y))

        return maximum            
```

#### **# Complexity**
- **Time Complexity**:  
  \(O(m * n)\), where \(m\) and \(n\) are the dimensions of the grid.  
  - Each cell is visited exactly once during the DFS traversal.  
  - Each recursive call processes up to 4 directions (a constant factor).  

- **Space Complexity**:  
  \(O(m * n)\) in the worst case (if the grid is one large connected component), due to the recursion stack.  

---


### BFS Solution

---

#### **# Intuition**
The problem can also be solved using a **breadth-first search (BFS)**, which explores a connected component level by level. BFS uses a queue to manage the exploration of valid neighbors. This approach allows systematic exploration and accumulation of fish counts, ensuring every component is processed.

---

#### **# Approach**
1. **Initialize Variables**:
   - Use a queue (`deque`) to manage cells to visit.
   - Implement a BFS function to explore all valid neighbors for a given starting cell.

2. **BFS Traversal**:
   - Start from a cell with non-zero fish.
   - Add the current cell's fish count to the total, mark it as visited by setting its value to \(0\), and enqueue all valid neighbors.

3. **Iterate Over the Grid**:
   - For each cell in the grid, if it is non-zero, invoke the BFS function to calculate the total fish in that connected component.
   - Update the maximum fish count.

4. **Return the Result**:
   - After visiting all cells, return the maximum fish count.

---


# Code

```
class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:

        def bfs():
            maxi = 0
            while queue:
                x,y = queue.popleft()
                maxi += grid[x][y]
                grid[x][y] = 0

                directions = [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]
                for r,c in directions:
                    if 0<=r< len(grid) and 0<=c < len(grid[0]) and grid[r][c] !=0:
                        queue.append((r,c))
            return maxi            

        queue = deque()
        maxFish = 0
        for x in range(len(grid)):
            for y in range(len(grid[0])):
                if grid[x][y] !=0:
                   queue.append((x,y)) 
                   maxFish = max(maxFish,bfs())

        return maxFish
```    

#### **# Complexity**
- **Time Complexity**:  
  \(O(m * n)\), where \(m\) and \(n\) are the dimensions of the grid.  
  - Each cell is visited exactly once during the BFS traversal.  
  - Each cell's neighbors are processed up to 4 times (constant factor).  

- **Space Complexity**:  
  \(O(m * n)\) in the worst case, for the queue (if all cells are part of the same connected component).  

---

### Comparison
- **DFS** is often faster in practice due to lower overhead, as it uses the call stack for traversal instead of explicit queue management.  
- **BFS** might be preferred for grids with very large components, as it avoids potential stack overflow issues in DFS.  
    



['Python3']