2658. Maximum Number of Fish in a Grid
Medium
30 Points
Array
Depth-First Search
Breadth-First Search
Union Find
Matrix
You are given a 0-indexed 2D matrix grid of size m x n, where (r, c) represents:
A fisher can start at any water cell (r, c) and can do the following operations any number of times:
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
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
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.lengthn == grid[i].length1 <= m, n <= 100 <= grid[i][j] <= 10
2658. Maximum Number of Fish in a Grid
Medium
30 Points
Array
Depth-First Search
Breadth-First Search
Union Find
Matrix
You are given a 0-indexed 2D matrix grid of size m x n, where (r, c) represents:
A fisher can start at any water cell (r, c) and can do the following operations any number of times:
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
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
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.lengthn == grid[i].length1 <= m, n <= 100 <= grid[i][j] <= 10