Maximum Number of Fish in a Grid
Problem Statement
Aapko ek 0-indexed 2D matrix
grid
di gayi hai jiska sizem x n
hai, jahan(r, c)
represent karta hai:Land cell agar
grid[r][c] = 0
.Water cell containing fish agar
grid[r][c]
greater than0
.
Operations a Fisher can Perform:
Fisher kisi bhi water cell
(r, c)
se start kar sakta hai aur yeh operations kar sakta hai:Catch all the fish at cell
(r, c)
.Move to any adjacent water cell (ek se connected water cells).
Objective:
Fisher ko aise start karna hai taki woh maximum number of fish catch kar sake. Agar koi water cell hi nahi hai to output
0
hoga.Adjacent Cells:
Adjacency rules mein, ek cell
(r, c)
ke adjacent cells ho sakte hain(r, c + 1)
,(r, c - 1)
,(r + 1, c)
ya(r - 1, c)
agar yeh cells exist karte hain.Examples:
Example 1:
Input:
grid = [[0,2,1,0], [4,0,0,3], [1,0,0,4], [0,3,2,0]]
Output:7
Explanation: Fisher cell(1,3)
se start karke 3 fish collect kar sakta hai, phir woh cell(2,3)
pe move karke additional 4 fish collect kar sakta hai. Total fish: 7.Example 2:
Input:
grid = [[1,0,0,0], [0,0,0,0], [0,0,0,0], [0,0,0,1]]
Output:1
Explanation: Fisher cells(0,0)
ya(3,3)
se start kar ke sirf ek hi fish collect kar sakta hai.Constraints:
m = grid.length
n = grid[0].length
1 <= m, n <= 10
0 <= grid[i][j] <= 10
In short, Fisher ko aise water cell se start karna hai taki woh maximum number of fish collect kar sake by moving to adjacent cells. Agar koi water cell available nahi hai to output
0
hoga.
Maximum Number of Fish in a Grid
Is problem ka main aim hai ek connected area mein maximum number of fish catch karna. Matlab, humein aisa path follow karna hoga jo highest number of fish provide kare.
Intuition
DFS (Depth-First Search) Use Karna: Depth-first search ek algorithm hai jise connected cells ko explore karne ke liye use kiya jata hai.Connected Cells: Humein har water cell ke adjacent water cells check karne hain aur unme jitni bhi fish hain unhe sum karna hai.
Approach
Time Complexity: O(m * n)
Grid Size: Aapko ek
m x n
size ka grid diya gaya hai, jahanm
rows aurn
columns hain.DFS Traversal: DFS (Depth-First Search) algorithm ke liye, humein har cell ko at least ek baar visit karna padta hai.
Total Cells: Total cells grid mein hain
m * n
.Har cell ko sirf ek baar visit karne ki wajah se, overall time complexity
O(m * n)
hoti hai.
Yani, apne grid ke sabhi cells ko traverse karne mein O(m * n)
time lagega.
Space Complexity: O(m * n)
Recursive Call Stack: DFS algorithm ek recursive function hai jo call stack use karta hai. Worst-case scenario mein, har cell ko visit karte hui maximum depth
m * n
cells tak ho sakti hai.Visited Array: Ek visited array use karte hain to track visited cells. Is array ko bhi
m * n
space chahiye hota hai.Total Space Used: Isliye, total space complexity bhi
O(m * n)
hoti hai.
Solution
class Solution {
// Directions array banate hain. Yeh directions ko represent karta hai: up, down, left, right
constructor() {
this.directions = [
[0, 1], [0, -1],
[1, 0], [-1, 0]
];
}
// Maximum fish find karne ka function
findMaxFish(grid) {
const m = grid.length;
const n = grid[0].length;
let maxFish = 0; // Initialize maximum fish count
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 0) continue; // Agar land cell hai to continue
// DFS call karke max fish update karte hain
maxFish = Math.max(maxFish, this.dfs(grid, i, j, m, n));
}
}
return maxFish; // Maximum fish count return karte hain
}
// Depth-First Search (DFS) algorithm to explore connected water cells
dfs(grid, i, j, m, n) {
let fish = 0;
if (grid[i][j] === 0) return fish; // Agar land cell hai to fish=0 return karte hain
fish += grid[i][j]; // Current cell ki fish count include karte hain
grid[i][j] = -1; // Mark karte hain ki visit ho gaya hai (visited)
// Adjacent cells ko explore karte hain using DFS
for (let dir of this.directions) {
const nr = i + dir[0]; // Next row index
const nc = j + dir[1]; // Next column index
if (nr >= 0 && nr < m && nc >= 0 && nc < n) { // Check karte hain ki cell grid ke boundaries mein hai ya nahi
if (grid[nr][nc] > 0) {
fish += this.dfs(grid, nr, nc, m, n); // DFS call karte hain for connected water cells
}
}
}
return fish; // Total fish count for connected component return karte hain
}
}
Class and Constructor:
Class Definition: The solution is wrapped inside a class named
Solution
.Directions Array: Inside the constructor, there’s a directions array that represents four possible movements (up, down, left, right).
findMaxFish Method:
Initialize Variables: This method initializes the necessary variables to track the number of rows (
m
) and columns (n
) in the grid, and a variablemaxFish
to keep track of the maximum fish caught.Iterate through Grid: It iterates through each cell of the grid.
Skip Land Cells: If the cell is a land cell (0), it continues to the next cell.
Call DFS: For each water cell, it calls the DFS function to explore all connected water cells and updates
maxFish
with the maximum fish caught from a connected component.
dfs (Depth-First Search) Method:
Initialize Fish Count: This method initializes a variable
fish
to keep track of the number of fish caught.Base Condition: If the current cell is a land cell (0), it returns 0 fish.
Catch Fish: It adds the number of fish in the current cell to the
fish
count and marks the cell as visited by setting its value to -1.Explore Adjacent Cells: It then explores all adjacent cells (up, down, left, right) using DFS. If an adjacent cell is within the grid boundaries and has fish, it recursively calls DFS to catch fish from connected cells.
Return Total Fish: Finally, it returns the total fish caught from the connected component.
Execution:
Grid Traversal: The
findMaxFish
method ensures that each cell in the grid is considered as a potential starting point to catch fish, and thedfs
method explores all connected water cells to find the maximum fish the fisher can catch.
Solution
class Solution {
public:
vector> directions = {{0,1}, {0,-1}, {1,0}, {-1,0}}; // Directions array for moving up, down, left, right
int findMaxFish(vector>& grid) {
int m = grid.size();
int n = grid[0].size();
int maxFish = 0; // Maximum fish count initialize karte hain
for(int i = 0; i < m; i++){ // Traverse har row
for(int j = 0; j < n; j++){ // Traverse har column
if(grid[i][j] == 0) continue; // Agar land cell hai, to skip karte hain
maxFish = max(maxFish, dfs(grid, i, j, m, n)); // DFS function call karte hain aur maximum fish update karte hain
}
}
return maxFish; // Maximum fish count return karte hain
}
private:
int dfs(vector>& grid, int i, int j, int m, int n){
int fish = 0; // Fish count initialize karte hain
if(grid[i][j] == 0) return fish; // Agar land cell hai to 0 fish return karte hain
fish += grid[i][j]; // Current cell ki fish count add karte hain
grid[i][j] = -1; // Current cell ko visited mark karte hain
for(const auto& dir : directions){ // Har direction ko traverse karte hain
int nr = i + dir[0]; // Next row index
int nc = j + dir[1]; // Next column index
if(nr >= 0 && nr < m && nc >= 0 && nc < n){ // Check karte hain ki cell grid boundaries mein hai ya nahi
if(grid[nr][nc] > 0){
fish += dfs(grid, nr, nc, m, n); // DFS call karte hain for connected water cells
}
}
}
return fish; // Total fish count return karte hain
}
};
Yeh code ek grid mein maximum number of fish ko catch karne ke liye banaya gaya hai. Usme ek
class
hai joSolution
ke naam se define ki gayi hai. Do main methods use kiye gaye hain – ek grid mein maximum fish find karne ke liye aur dusra depth-first search (DFS) algorithm use karke connected cells ko explore karne ke liye.Directions Array:
Constructor mein ek directions array define ki gayi hai jismein four possible movements (up, down, left, right) store ki gaye hain.
findMaxFish Method:
Initialize Variables: Code sabse pehle grid ka size nikalta hai
(m, n)
aur ek variablemaxFish
initialize karta hai zero se.Iterate Grid: Yeh method grid ke har row aur column ko traverse karta hai.
Skip Land Cells: Agar koi cell
0
(land cell) hai to usse skip karte hain.Call DFS: Har water cell ke liye, state ko maximum fish se update karte hain using
dfs
method jo connected water cells ko explore kar raha hota hai.
dfs (Depth-First Search) Method:
Initialize Fish Count: Yeh method ek variable
fish
initialize karta hai zero se.Base Condition: Agar current cell land cell (0) hai, to yeh
0
fish return karta hai.Catch Fish: Current cell ki fish count ko total
fish
main add karta hai and cell ko mark karta hai as visited by setting value to-1
.Explore Adjacent Cells: Yeh method adjacent cells ko check karta hai using DFS:
Boundaries Check: Check karta hai ki adjacent cell within grid boundaries hai ya nahi.
Recursion: Agar adjacent cell water cell hai, to
dfs
method ko recursively call karta hai.
Return Total Fish: Finally, total fish count return karta hai for the connected component.
Execution:
Grid Traversal:
findMaxFish
method ensure karta hai ki har cell ko consider kiya jaye as potential starting point to catch fish, aurdfs
method deep mein jaake saare connected water cells ko explore karta hai to find maximum fish count.