✔💯 DAY 394  | DFS vs BFS | 100% 0ms | [PYTHON/JAVA/C++] | EXPLAINED | Approach 💫
Please Upvote as it really motivates me \uD83C\uDD99\uD83C\uDD99\uD83C\uDD99\n# Intuition & Approach\n Describe your approach to solving the problem. \n##### \u
# Please Upvote as it really motivates me \uD83C\uDD99\uD83C\uDD99\uD83C\uDD99\n# Intuition & Approach\n<!-- Describe your approach to solving the problem. -->\n##### \u2022\tWe are given a 2D matrix grid representing land cells and water cells containing fish.\n##### \u2022\tWe need to find the maximum number of fish that can be caught by a fisher starting from any water cell.\n##### \u2022\tWe can start by iterating over all water cells in the grid and using a depth-first search (DFS) to explore all adjacent water cells and calculate the maximum number of fish that can be caught starting from that cell.\n##### \u2022\tIn the DFS, we start with the current water cell and explore all adjacent water cells using a 2D array  dr that contains the four possible directions. For each adjacent water cell, we calculate the total number of fish that can be caught starting from the current cell and add it to the maximum number of fish caught so far. We also remove each water cell from the map as we visit it to avoid visiting the same cell twice.\n##### \u2022\tWe keep track of the maximum number of fish caught so far and return it as the answer.\n##### \u2022\tSince we explore each water cell in the grid only once and perform constant time operations for each cell, the time complexity of this solution is O(n), where n is the total number of cells in the grid.\n##### \u2022\tWe can also optimize the solution by using memoization to avoid recomputing the maximum number of fish caught starting from a water cell that has already been visited.\n\n\n\n# Code\n```java []\npublic int findFish(int[][] grid) {\n    int n = grid.length;\n    int m = grid[0].length;\n    int maxFish = 0; // variable to store the maximum number of fish caught\n    for(int i = 0; i < n; i++) {\n        for(int j = 0; j < m; j++) {\n            if(grid[i][j] > 0) { // if the current cell contains fish\n                maxFish = Math.max(maxFish, dfs(i, j, grid, n, m)); // update the maximum number of fish caught\n            }\n        }\n    }\n    return maxFish; // return the maximum number of fish caught\n}\n\n// array to store the four possible directions\nprivate final int[] dr = {0, 1, 0, -1, 0};\n\n// function to perform DFS and count the number of fish caught\nint dfs(int i, int j, int[][] grid, int n, int m) {\n    int fish = grid[i][j]; // count the number of fish caught in the current cell\n    grid[i][j] = 0; // mark the current cell as visited by setting its value to 0\n    for(int k = 0; k < 4; k++) { // iterate over the four possible directions\n        int nr = i + dr[k], nc = j + dr[k + 1]; // calculate the coordinates of the adjacent cell\n        if(nr < n && nr >= 0 && nc < m && nc >= 0 && grid[nr][nc] > 0) { // if the adjacent cell contains fish and is within the grid\n            fish += dfs(nr, nc, grid, n, m); // count the number of fish caught in the adjacent cell\n        }\n    }\n    return fish; // return the total number of fish caught\n}\n```\n```c++ []\nint findMaxFish(vector<vector<int>>& grid) {\n    int n = grid.size();\n    int m = grid[0].size();\n    int ans = 0;\n    for(int i = 0; i < n; i++) {\n        for(int j = 0; j < m; j++) {\n            if(grid[i][j] > 0) {\n                ans = max(ans, dfs(i, j, grid, n, m));\n            }\n        }\n    }\n    return ans;\n}\nint dfs(int i, int j, vector<vector<int>>& grid, int n, int m) {\n    int f = grid[i][j];\n    grid[i][j] = 0;\n    int dr[] = {0, 1, 0, -1, 0};\n    for(int k = 0; k < 4; k++) {\n        int nr = i + dr[k];\n        int nc = j + dr[k + 1];\n        if(nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] > 0) {\n            f += dfs(nr, nc, grid, n, m);\n        }\n    }\n    return f;\n}\n```\n```python []\ndef findMaxFish(self, grid: List[List[int]]) -> int:\n    n = len(grid)\n    m = len(grid[0])\n    ans = 0\n    for i in range(n):\n        for j in range(m):\n            if grid[i][j] > 0:\n                ans = max(ans, self.dfs(i, j, grid, n, m))\n    return ans\n\ndef dfs(self, i: int, j: int, grid: List[List[int]], n: int, m: int) -> int:\n    f = grid[i][j]\n    grid[i][j] = 0\n    dr = [0, 1, 0, -1, 0]\n    for k in range(4):\n        nr = i + dr[k]\n        nc = j + dr[k + 1]\n        if nr >= 0 and nr < n and nc >= 0 and nc < m and grid[nr][nc] > 0:\n            f += self.dfs(nr, nc, grid, n, m)\n    return f\n```\n\n# Please Upvote as it really motivates me \uD83C\uDD99\uD83C\uDD99\uD83C\uDD99\n\n\n# BFS \n\nWe start by iterating over all water cells in the grid and checking if they contain fish. If a water cell contains fish, we add it to a queue and start the BFS. We also set the value of the current water cell to 0 to mark it as visited.\n\nIn the BFS, we explore all adjacent water cells using two arrays  dr and  dc that contain the four possible directions. For each adjacent water cell, we add the number of fish it contains to the total number of fish caught so far and mark it as visited by setting its value to 0. We also add it to the queue to explore its adjacent water cells in the next iteration.\n\nAfter the BFS is complete, we update the maximum number of fish caught so far and continue iterating over the remaining water cells.\n\nSince we explore each water cell in the grid only once and perform constant time operations for each cell, the time complexity of this solution is O(n), where n is the total number of cells in the grid.\n```java []\nint findMaxFish[][] grid) {\n    int n = grid.length;\n    int m = grid[0].length;\n    int ans = 0; // variable to store the maximum number of fish caught\n    int[] dr = {0, 1, 0, -1}; // array to store the four possible directions\n    int[] dc = {1, 0, -1, 0};\n    for(int i = 0; i < n; i++) {\n        for(int j = 0; j < m; j++) {\n            if(grid[i][j] > 0) { // if the current cell contains fish\n                Queue<int[]> q = new LinkedList<>(); // create a queue to perform BFS\n                q.offer(new int[]{i, j}); // add the current cell to the queue\n                int f = grid[i][j]; // count the number of fish caught in the current cell\n                grid[i][j] = 0; // mark the current cell as visited by setting its value to 0\n                while(!q.isEmpty()) { // while there are cells in the queue\n                    int[] curr = q.poll(); // remove the first cell from the queue\n                    for(int k = 0; k < 4; k++) { // iterate over the four possible directions\n                        int nr = curr[0] + dr[k]; // calculate the coordinates of the adjacent cell\n                        int nc = curr[1] + dc[k];\n                        if(nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] > 0) { // if the adjacent cell contains fish and is within the grid\n                            f += grid[nr][nc]; // count the number of fish caught in the adjacent cell\n                            grid[nr][nc] = 0; // mark the adjacent cell as visited by setting its value to 0\n                            q.offer(new int[]{nr, nc}); // add the adjacent cell to the queue\n                        }\n                    }\n                }\n                ans = Math.max(ans, f); // update the maximum number of fish caught so far\n            }\n        }\n    }\n    return ans; // return the maximum number of fish caught\n}\n```\n```c++ []\nclass Solutionpublic:\n    int findMaxFish(vector<vector<int>>& grid) {\n        int n = grid.size();\n        int m = grid[0].size();\n        int ans = 0;\n        vector<int> dr = {0, 1, 0, -1};\n        vector<int> dc = {1, 0, -1, 0};\n        for(int i = 0; i < n; i++) {\n            for(int j = 0; j < m; j++) {\n                if(grid[i][j] > 0) {\n                    queue<pair<int, int>> q;\n                    q.push({i, j});\n                    int f = grid[i][j];\n                    grid[i][j] = 0;\n                    while(!q.empty()) {\n                        auto curr = q.front();\n                        q.pop();\n                        for(int k = 0; k < 4; k++) {\n                            int nr = curr.first + dr[k];\n                            int nc = curr.second + dc[k];\n                            if(nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] > 0) {\n                                f += grid[nr][nc];\n                                grid[nr][nc] = 0;\n                                q.push({nr, nc});\n                            }\n                        }\n                    }\n                    ans = max(ans, f);\n                }\n            }\n        }\n        return ans;\n    }\n};\n```\n```python []\nclass Solution:\n    def findMaxFish(self, grid: List[List[int]]) -> int:\n        n = len(grid)\n        m = len(grid[0])\n        ans = 0\n        dr = [0, 1, 0, -1]\n        dc = [1, 0, -1, 0]\n        for i in range(n):\n            for j in range(m):\n                if grid[i][j] > 0:\n                    q = deque()\n                    q.append((i, j))\n                    f = grid[i][j]\n                    grid[i][j] = 0\n                    while q:\n                        curr = q.popleft()\n                        for k in range(4):\n                            nr = curr[0] + dr[k]\n                            nc = curr[1] + dc[k]\n                            if nr >= 0 and nr < n and nc >= 0 and nc < m and grid[nr][nc] > 0:\n                                f += grid[nr][nc]\n                                grid[nr][nc] = 0\n                                q.append((nr, nc))\n                    ans = max(ans, f)\n        return ans\n```\n\n![BREUSELEE.webp](https://assets.leetcode.com/users/images/062630f0-ef80-4e74-abdb-302827b99235_1680054012.5054147.webp)\n![image.png](https://assets.leetcode.com/users/images/303fa18d-281d-49f0-87ef-1a018fc9a488_1681355186.0923774.png)\n\n\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\nThanks for visiting my solution.\uD83D\uDE0A Keep Learning\nPlease give my solution an upvote! \uD83D\uDC4D \uD83C\uDD99\uD83C\uDD99\uD83C\uDD99\nhttps://leetcode.com/problems/maximum-number-of-fish-in-a-grid/solutions/3466649/day-394-100-0ms-python-java-c-explained-approach/\nIt\'s a simple way to show your appreciation and\nkeep me motivated. Thank you! \uD83D\uDE0A
['Depth-First Search', 'Python', 'C++', 'Java', 'Python3']