Leetcode 2658: Maximum Number of Fish in a Grid
You are given a 2D matrix
grid of size m x n, where each cell can either be a land cell (represented by 0) or a water cell (represented by a positive integer indicating the number of fish present in that cell). A fisher can start at any water cell and perform two operations any number of times: catch all the fish in the current cell or move to an adjacent water cell. Your task is to determine the maximum number of fish the fisher can catch if they start at the optimal water cell.Problem
Approach
Steps
Complexity
Input: You are given a 2D grid of integers, where 0 represents a land cell and a positive integer represents a water cell containing that many fish.
Example: Input: grid = [[0, 3, 2], [4, 0, 0], [1, 0, 3]]
Constraints:
• 1 <= m, n <= 10
• 0 <= grid[i][j] <= 10
Output: Return the maximum number of fish the fisher can catch by starting at the optimal water cell.
Example: Output: 9
Constraints:
• The output should be a single integer representing the maximum number of fish the fisher can catch.
Goal: The goal is to find the maximum number of fish that can be caught starting from any water cell, including moving through adjacent water cells.
Steps:
• Step 1: Iterate over each water cell in the grid.
• Step 2: For each water cell, perform a Depth-First Search (DFS) to count the total number of fish that can be caught starting from that cell and moving through adjacent water cells.
• Step 3: Track the maximum fish count found during the search.
Goal: The solution needs to respect the grid size constraints and ensure all operations are performed efficiently within these bounds.
Steps:
• Grid dimensions are at most 10x10, which allows for a depth-first search (DFS) to be performed within time limits.
Assumptions:
• The grid will contain at least one water cell.
• Input: Input: grid = [[0, 3, 2], [4, 0, 0], [1, 0, 3]]
• Explanation: Starting at cell (0, 1), the fisher can catch 3 fish. Then, they can move to (1, 0) and catch 4 more fish. A total of 9 fish can be caught.
• Input: Input: grid = [[1, 0, 0], [0, 0, 0], [0, 0, 1]]
• Explanation: The fisher can start at either (0, 0) or (2, 2) and catch 1 fish.
Approach: The approach involves performing a Depth-First Search (DFS) from each water cell to find the maximum number of fish the fisher can catch. We explore all adjacent water cells recursively to accumulate the number of fish and track the maximum fish count.
Observations:
• We need to explore the grid cell by cell, performing a DFS to count fish from each starting point.
• The DFS will help us explore all possible reachable water cells from any starting cell to accumulate the maximum fish count.
Steps:
• Step 1: Iterate over all cells in the grid. If the current cell is a water cell (grid[i][j] > 0), perform a DFS from that cell.
• Step 2: In the DFS, mark cells as visited by setting grid[i][j] to 0, and accumulate the number of fish collected.
• Step 3: Check all adjacent cells (up, down, left, right) during the DFS, recursively adding their fish counts if they are also water cells.
• Step 4: Return the maximum accumulated fish count.
Empty Inputs:
• An empty grid should not be passed as per the constraints.
Large Inputs:
• The grid size is small (maximum 10x10), so large input grids are not a concern.
Special Values:
• A grid with no fish should return 0.
Constraints:
• Ensure to handle cases where there are no water cells (i.e., the grid only contains land cells).
int m, n;
vector<vector<int>> grid;
int findMaxFish(vector<vector<int>>& grid) {
m = grid.size(), n = grid[0].size();
this->grid = grid;
int mx = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(grid[i][j] != 0) {
mx = max(mx, dfs(i, j));
}
return mx;
}
int dfs(int i, int j) {
if(i >= m || j >= n || i < 0 || j < 0 || grid[i][j] == 0) return 0;
int ans = grid[i][j];
grid[i][j] = 0;
ans += dfs(i + 1, j);
ans += dfs(i - 1, j);
ans += dfs(i, j + 1);
ans += dfs(i, j - 1);
return ans;
}
1 : Variable Declaration
int m, n;
This line declares two integer variables 'm' and 'n' to store the dimensions of the grid.
2 : Grid Declaration
vector<vector<int>> grid;
A 2D vector 'grid' is declared to store the fish grid values.
3 : Function Definition
int findMaxFish(vector<vector<int>>& grid) {
This defines the function 'findMaxFish', which takes the 2D grid as input and returns the maximum amount of fish that can be collected.
4 : Grid Initialization
m = grid.size(), n = grid[0].size();
The dimensions of the grid are calculated and stored in 'm' and 'n'.
5 : Grid Assignment
this->grid = grid;
The input grid is assigned to the member variable 'grid' for later use in the DFS function.
6 : Variable Initialization
int mx = 0;
A variable 'mx' is initialized to 0, which will store the maximum number of fish collected during the DFS search.
7 : Outer Loop
for(int i = 0; i < m; i++)
An outer loop starts to iterate through each row of the grid.
8 : Inner Loop
for(int j = 0; j < n; j++)
An inner loop iterates through each column in the current row of the grid.
9 : Fish Check
if(grid[i][j] != 0) {
This checks if the current grid cell contains fish (value is not 0).
10 : DFS Call
mx = max(mx, dfs(i, j));
If the current cell contains fish, the DFS function is called from this cell, and the maximum number of fish collected is updated.
11 : Return Maximum Fish
return mx;
The function returns the maximum number of fish collected.
12 : DFS Function Definition
int dfs(int i, int j) {
This defines the DFS function that explores the grid and collects fish from the adjacent cells.
13 : DFS Boundary Check
if(i >= m || j >= n || i < 0 || j < 0 || grid[i][j] == 0) return 0;
This line checks for out-of-bounds indices or cells that don't contain fish (value 0), and returns 0 if any condition is met.
14 : Fish Collection
int ans = grid[i][j];
The variable 'ans' is initialized to the current cell's value (the amount of fish at that cell).
15 : Grid Update
grid[i][j] = 0;
The current grid cell is marked as visited by setting its value to 0.
16 : Recursive DFS Calls
ans += dfs(i + 1, j);
The DFS function is called recursively for the adjacent cell below the current one.
17 : Recursive DFS Calls
ans += dfs(i - 1, j);
The DFS function is called recursively for the adjacent cell above the current one.
18 : Recursive DFS Calls
ans += dfs(i, j + 1);
The DFS function is called recursively for the adjacent cell to the right of the current one.
19 : Recursive DFS Calls
ans += dfs(i, j - 1);
The DFS function is called recursively for the adjacent cell to the left of the current one.
20 : Return Fish Count
return ans;
The total number of fish collected from the current cell and its adjacent cells is returned.
Best Case: O(m * n)
Average Case: O(m * n)
Worst Case: O(m * n)
Description: The worst-case time complexity is O(m * n) due to the DFS traversal of all grid cells in the grid of size m x n.
Best Case: O(m * n)
Worst Case: O(m * n)
Description: The space complexity is O(m * n) due to the stack used by the DFS to explore all cells.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus