Problem

You are given a 0-indexed 2D matrix grid of size m x n, where (r, c) represents:

  • A land cell if grid[r][c] = 0, or
  • A water cell containing grid[r][c] fish, if grid[r][c] > 0.

A fisher can start at any water cell (r, c) and can do the following operations any number of times:

  • Catch all the fish at cell (r, c), or
  • Move to any adjacent water cell.

Return the maximum number of fish the fisher can catch if he chooses his starting cell optimally, or 0 if no water cell exists.

An adjacent cell of the cell (r, c), is one of the cells (r, c + 1), (r, c - 1), (r + 1, c) or (r - 1, c) if it exists.

Examples

Example 1:

$$ \begin{array}{|c|c|c|c|} \hline 0 & 2 & 1 & 0 \\ \hline 4 & 0 & 0 & 3 \\ \hline 1 & 0 & 0 & 4 \\ \hline 0 & 3 & 2 & 0 \\ \hline \end{array} $$

1
2
3

Input: grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
Output: 7
Explanation: The fisher can start at cell (1,3) and collect 3 fish, then move to cell (2,3) and collect 4 fish.

Example 2:

$$ \begin{array}{|c|c|c|c|} \hline 1 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 1 \\ \hline \end{array} $$

1
2
3

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
Output: 1
Explanation: The fisher can start at cells (0,0) or (3,3) and collect a single fish.

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • 0 <= grid[i][j] <= 10

Solution

Method 1 - DFS

  • To solve the problem of finding the maximum number of fish a fisher can catch by starting from any water cell and moving to adjacent water cells, we can approach it as a graph traversal problem.
  • We will use Depth-First Search (DFS) to explore all possible water cells from a given starting point and calculate the total fish that can be caught.]

Approach

  1. Graph Representation and Traversal:
    • Each cell in the grid is a node.
    • There are edges between nodes if they are adjacent and both contain water.
  2. DFS Implementation:
    • Perform DFS starting from each water cell, marking visited cells to avoid recounting.
    • For each DFS traversal, track the number of fish caught.
    • Update the global maximum whenever a higher count is found.
  3. Edge Cases:
    • If there are no water cells at all, return 0.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    public int findMaxFish(int[][] grid) {
        int ans = 0, m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0 && !visited[i][j]) {
                    ans = Math.max(ans, dfs(grid, visited, i, j));
                }
            }
        }
        
        return ans;
    }

	private final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	private int dfs(int[][] grid, boolean[][] visited, int r, int c) {
	    if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || 
	        grid[r][c] == 0 || visited[r][c]) {
	        return 0;
	    }
	
	    visited[r][c] = true;
	    int fish = grid[r][c];
	
	    for (int[] dir : dirs) {
	        fish += dfs(grid, visited, r + dir[0], c + dir[1]);
	    }
	
	    return fish;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    
    def findMaxFish(self, g: List[List[int]]) -> int:
        m, n = len(g), len(g[0])
        vis = [[False] * n for _ in range(m)]
        ans = 0
        
        for i in range(m):
            for j in range(n):
                if g[i][j] > 0 and not vis[i][j]:
                    ans = max(ans, self.dfs(g, i, j, vis))
        
        return ans
    
    def dfs(self, g: List[List[int]], r: int, c: int, vis: List[List[bool]]) -> int:
        if r < 0 or c < 0 or r >= len(g) or c >= len(g[0]) or g[r][c] == 0 or vis[r][c]:
            return 0
        vis[r][c] = True
        fish = g[r][c]
        fish += self.dfs(g, r + 1, c, vis)
        fish += self.dfs(g, r - 1, c, vis)
        fish += self.dfs(g, r, c + 1, vis)
        fish += self.dfs(g, r, c - 1, vis)
        return fish

Complexity

  • ⏰ Time complexity: O(m * n) where m is the number of rows and n is the number of columns. Each cell is visited once.
  • 🧺 Space complexity: O(m * n) for the recursion stack and the visited matrix.