Explained | C++ | Java | DFS | BFS | Beginner Friendly Code |
DFS Approach\n\n\n1. Define a helper function dfs that takes the grid, the row index r, and the column index c as arguments. The function returns the total numb
**DFS Approach**\n\n```\n1. Define a helper function dfs that takes the grid, the row index r, and the column index c as arguments. The function returns the total number of fish caught starting from the cell (r, c).\n2. In the dfs function, check if the current cell is out of bounds or a land cell. If so, return 0 (base case).\n3. Otherwise, catch the fish at the current cell by storing its value in a variable fishCaught.\n4. Mark the current cell as caught by setting its value to 0 in the grid.\n5. Define an array moves that contains the possible movements of the fisherman. Each movement is defined as an array of two integers, representing the change in row and column indices, respectively.\n6. For each possible movement in moves, calculate the new cell coordinates by adding the movement to the current cell coordinates.\n7. Recursively call the dfs function with the new cell coordinates, and add the result to fishCaught.\n8. Return fishCaught.\n9. In the findMaxFish function, initialize a variable maxFish to 0 to keep track of the maximum number of fish caught by the fisherman.\n10. Iterate over every cell in the grid.\n11. For each water cell (i.e., cells with a positive value), start a DFS search using the dfs function to find the maximum number of fish that can be caught starting from this cell.\n12. Update maxFish to the maximum value between maxFish and the number of fish caught starting from the current water cell.\n13. Return maxFish.\n```\n\n**C++ Code For DFS Approach**\n```\nint dfs(vector<vector<int>>& grid, int r, int c) {\n    if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() || grid[r][c] == 0) {\n        return 0; // Base case: out of bounds or land cell\n    }\n    int fishCaught = grid[r][c]; // Catch fish at current cell\n    grid[r][c] = 0; // Mark cell as caught\n    int moves[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // Possible movements\n    for (int i = 0; i < 4; i++) {\n        int newR = r + moves[i][0];\n        int newC = c + moves[i][1];\n        fishCaught += dfs(grid, newR, newC); // Recursively search adjacent cells\n    }\n    return fishCaught;\n}\n\nint findMaxFish(vector<vector<int>>& grid) {\n    int maxFish = 0;\n    for (int i = 0; i < grid.size(); i++) {\n        for (int j = 0; j < grid[0].size(); j++) {\n            if (grid[i][j] > 0) { // Start DFS search from water cell\n                int fishCaught = dfs(grid, i, j);\n                maxFish = max(maxFish, fishCaught);\n            }\n        }\n    }\n    return maxFish;\n}\n```\n\n**Java Code For DFS Approach**\n```\npublic int dfs(int[][] grid, int r, int c) {\n    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0) {\n        return 0; // Base case: out of bounds or land cell\n    }\n    int fishCaught = grid[r][c]; // Catch fish at current cell\n    grid[r][c] = 0; // Mark cell as caught\n    int[][] moves = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // Possible movements\n    for (int[] move : moves) {\n        int newR = r + move[0];\n        int newC = c + move[1];\n        fishCaught += dfs(grid, newR, newC); // Recursively search adjacent cells\n    }\n    return fishCaught;\n}\n\npublic int findMaxFish(int[][] grid) {\n    int maxFish = 0;\n    for (int i = 0; i < grid.length; i++) {\n        for (int j = 0; j < grid[0].length; j++) {\n            if (grid[i][j] > 0) { // Start DFS search from water cell\n                int fishCaught = dfs(grid, i, j);\n                maxFish = Math.max(maxFish, fishCaught);\n            }\n        }\n    }\n    return maxFish;\n}\n```\n\n**BFS Approach:**\n```\n1. Initialize a variable maxFish to 0 to keep track of the maximum number of fish caught by the fisherman.\n2. Get the size of the grid m x n.\n3. Define a 2D array moves that contains the possible movements of the fisherman. Each movement is defined as an array of two integers, representing the change in row and column indices, respectively.\n4. Iterate over every cell in the grid.\n5. For each water cell (i.e., cells with a positive value), start a BFS search to find the maximum number of fish that can be caught starting from this cell.\n6. Initialize a queue and add the current water cell coordinates to the queue.\n7. Initialize a variable fishCaught to 0 to keep track of the number of fish caught starting from the current water cell.\n8. While the queue is not empty, do the following:\n\ta. Dequeue the front element of the queue, representing the current water cell coordinates.\n\tb. If the current cell contains fish (i.e., has a positive value), catch the fish and add its value to fishCaught. Set the     cell value to 0 to mark it as caught.\n\tc. Iterate over every possible movement in the moves array.\n\td. Calculate the new cell coordinates by adding the movement to the current cell coordinates.\n\te. If the new cell is within the bounds of the grid and is a water cell (i.e., has a positive value), add its coordinates     to the queue.\n9. Update maxFish to the maximum value between maxFish and fishCaught.\n10. Return maxFish.\n```\n\n**C++ Code For BFS Approach**\n```\nint findMaxFish(vector<vector<int>>& grid) {\n    int maxFish = 0;\n    int m = grid.size();\n    int n = grid[0].size();\n    \n    vector<vector<int>> moves = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // Possible moves\n    \n    for (int i = 0; i < m; i++) {\n        for (int j = 0; j < n; j++) {\n            if (grid[i][j] > 0) { // Start at a water cell\n                queue<pair<int, int>> q;\n                q.push({i, j});\n                int fishCaught = 0;\n                while (!q.empty()) {\n                    int r = q.front().first;\n                    int c = q.front().second;\n                    q.pop();\n                    if (grid[r][c] > 0) { // Catch fish at current cell\n                        fishCaught += grid[r][c];\n                        grid[r][c] = 0; // Mark cell as caught\n                    }\n                    for (auto& move : moves) { // Iterate over possible moves\n                        int newR = r + move[0];\n                        int newC = c + move[1];\n                        if (newR >= 0 && newR < m && newC >= 0 && newC < n && grid[newR][newC] > 0) {\n                            q.push({newR, newC}); // Add new water cell to queue\n                        }\n                    }\n                }\n                maxFish = max(maxFish, fishCaught);\n            }\n        }\n    }\n    \n    return maxFish;\n}\n```\n\n**Java Code For BFS Approach**\n\n```\npublic int findMaxFish(int[][] grid) {\n    int maxFish = 0;\n    int[][] moves = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // Possible movements\n    for (int i = 0; i < grid.length; i++) {\n        for (int j = 0; j < grid[0].length; j++) {\n            if (grid[i][j] > 0) { // Start BFS search from water cell\n                int fishCaught = 0;\n                Queue<int[]> queue = new LinkedList<>(); // Queue for BFS\n                queue.offer(new int[]{i, j}); // Enqueue current cell\n                while (!queue.isEmpty()) {\n                    int[] curr = queue.poll(); // Dequeue first cell\n                    int r = curr[0];\n                    int c = curr[1];\n                    if (grid[r][c] > 0) { // Catch fish at current cell\n                        fishCaught += grid[r][c];\n                        grid[r][c] = 0; // Mark cell as caught\n                    }\n                    for (int[] move : moves) {\n                        int newR = r + move[0];\n                        int newC = c + move[1];\n                        if (newR >= 0 && newR < grid.length && newC >= 0 && newC < grid[0].length && grid[newR][newC] > 0) {\n                            queue.offer(new int[]{newR, newC}); // Enqueue adjacent water cell\n                        }\n                    }\n                }\n                maxFish = Math.max(maxFish, fishCaught);\n            }\n        }\n    }\n    return maxFish;\n}\n```\n\n**PLEASE DO UPVOTE**
['Depth-First Search', 'Breadth-First Search', 'C', 'C++']