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, ifgrid[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} $$
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} $$
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
- 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.
- 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.
- 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
Java
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;
}
}
Python
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)
wherem
is the number of rows andn
is the number of columns. Each cell is visited once. - 🧺 Space complexity:
O(m * n)
for the recursion stack and the visited matrix.