Finding Maximum Fish with DFS 🐟💡
To solve this problem, we can use Depth-First Search (DFS) to explore connected regions of the grid. Here's the step-by-step approach:

Iterate Through the Grid
To solve this problem, we can use **Depth-First Search (DFS)** to explore connected regions of the grid. Here's the step-by-step approach:

1. **Iterate Through the Grid**: Loop through all cells in the grid. If a cell contains fish (`grid[i][j] > 0`), it is the starting point for a new connected region.

2. **Use DFS for Region Exploration**:
   - From the starting cell, recursively explore all its valid neighbors (up, down, left, right).
   - Add up the fish from all connected cells in the region.
   - Mark visited cells by setting them to `0` to prevent revisiting.

3. **Track Maximum Fish**:
   - After each DFS, compare the fish count from the current region to the maximum fish count found so far.

4. **Return the Result**: The largest fish count across all connected regions is the answer.

---

#### **Pseudocode**

```
1. Initialize `maxFish = 0`.
2. Define DFS function:
    - Take coordinates `x, y` as input.
    - If cell is out of bounds or contains `0`, return 0.
    - Otherwise:
        - Collect the fish from the cell.
        - Mark the cell as visited (set it to 0).
        - Recursively explore all 4 neighbors and add their fish to the current total.
        - Return the total fish collected from this region.
3. Iterate through all cells in the grid:
    - If cell contains fish, call DFS and update `maxFish`.
4. Return `maxFish`.
```

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

        def dfs(x, y):
            if x < 0 or x >= n or y < 0 or y >= m or grid[x][y] == 0:
                return 0

            fish = grid[x][y]
            grid[x][y] = 0  # Mark as visited

            for dx, dy in directions:
                fish += dfs(x + dx, y + dy)

            return fish

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

        return max_fish
```
```cpp []
class Solution {
public:
    int findMaxFish(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<int> dx = {-1, 0, 1, 0};
        vector<int> dy = {0, 1, 0, -1};

        auto dfs = [&](int x, int y, auto& dfs) -> int {
            if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) return 0;

            int fish = grid[x][y];
            grid[x][y] = 0;

            for (int d = 0; d < 4; ++d) {
                fish += dfs(x + dx[d], y + dy[d], dfs);
            }
            return fish;
        };

        int maxFish = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] > 0) {
                    maxFish = max(maxFish, dfs(i, j, dfs));
                }
            }
        }
        return maxFish;
    }
};
```
```golang []
func findMaxFish(grid [][]int) int {
    n := len(grid)
    m := len(grid[0])
    dx := []int{-1, 0, 1, 0}
    dy := []int{0, 1, 0, -1}

    var dfs func(x, y int) int
    dfs = func(x, y int) int {
        if x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0 {
            return 0
        }

        fish := grid[x][y]
        grid[x][y] = 0

        for d := 0; d < 4; d++ {
            fish += dfs(x+dx[d], y+dy[d])
        }
        return fish
    }

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

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
```
```csharp []
public class Solution {
    public int FindMaxFish(int[][] grid) {
        int n = grid.Length, m = grid[0].Length;
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        int Dfs(int x, int y) {
            if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) return 0;

            int fish = grid[x][y];
            grid[x][y] = 0;

            for (int d = 0; d < 4; d++) {
                fish += Dfs(x + dx[d], y + dy[d]);
            }
            return fish;
        }

        int maxFish = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] > 0) {
                    maxFish = Math.Max(maxFish, Dfs(i, j));
                }
            }
        }
        return maxFish;
    }
}
```
```java []
class Solution {
    public int findMaxFish(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        // DFS function
        int dfs(int x, int y) {
            if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) return 0;

            int fish = grid[x][y];
            grid[x][y] = 0;

            for (int d = 0; d < 4; d++) {
                fish += dfs(x + dx[d], y + dy[d]);
            }
            return fish;
        }

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

---
#### **Complexity Analysis**

- **Time Complexity**:  
  Each cell is visited **once** during DFS and marked as visited. Thus, the time complexity is $$ O(n \times m) $$, where $$ n $$ and $$ m $$ are the dimensions of the grid.

- **Space Complexity**:  
  The space complexity is $$ O(n \times m) $$ for the recursion stack in the worst case (if the entire grid is one connected region).

---

#### **Example Walkthrough**

**Input**:  
```
grid = [[0, 2, 0], 
        [4, 0, 5], 
        [0, 3, 0]]
```

**Steps**:
1. Start at cell (1, 0) (value 4). Perform DFS:
   - Collect fish: 4.
   - Stop DFS as no valid neighbors exist.

   Region total = 4.

2. Move to cell (0, 1) (value 2). Perform DFS:
   - Collect fish: 2.
   - Stop DFS as no valid neighbors exist.

   Region total = 2.

3. Move to cell (1, 2) (value 5). Perform DFS:
   - Collect fish: 5.
   - Stop DFS as no valid neighbors exist.

   Region total = 5.

4. Move to cell (2, 1) (value 3). Perform DFS:
   - Collect fish: 3.
   - Stop DFS as no valid neighbors exist.

   Region total = 3.

**Output**:  
The largest region has 5 fish, so the result is **5**.

---


['Array', 'Depth-First Search', 'Matrix', 'C++', 'Java', 'Go', 'Python3', 'C#']