Maximum Number of Fish in a Grid

Problem Statement

  • Aapko ek 0-indexed 2D matrix grid di gayi hai jiska size m 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 than 0.

    Operations a Fisher can Perform:

    Fisher kisi bhi water cell (r, c) se start kar sakta hai aur yeh operations kar sakta hai:

    1. Catch all the fish at cell (r, c).

    2. 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.

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.

Time Complexity: O(m * n)

  • Grid Size: Aapko ek m x n size ka grid diya gaya hai, jahan m rows aur n 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 variable maxFish 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 the dfs method explores all connected water cells to find the maximum fish the fisher can catch.

Solution

				
					class Solution {
public:
    vector<vector<int>> directions = {{0,1}, {0,-1}, {1,0}, {-1,0}}; // Directions array for moving up, down, left, right

    int findMaxFish(vector<vector<int>>& 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<vector<int>>& 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 jo Solution 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 variable maxFish 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, aur dfs method deep mein jaake saare connected water cells ko explore karta hai to find maximum fish count.