2658. Maximum Number of Fish in a Grid

• Time: $O(mn)$
• Space: $O(mn)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public: int findMaxFish(vector>& grid) { int ans = 0; for (int i = 0; i < grid.size(); ++i) for (int j = 0; j < grid[0].size(); ++j) if (grid[i][j] > 0) ans = max(ans, dfs(grid, i, j)); return ans; } private: int dfs(vector>& grid, int i, int j) { if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size()) return 0; if (grid[i][j] == 0) return 0; int caughtFish = grid[i][j]; grid[i][j] = 0; // Mark 0 as visited return caughtFish + // dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + // dfs(grid, i, j + 1) + dfs(grid, i, j - 1); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int findMaxFish(int[][] grid) { int ans = 0; for (int i = 0; i < grid.length; ++i) for (int j = 0; j < grid[0].length; ++j) if (grid[i][j] > 0) ans = Math.max(ans, dfs(grid, i, j)); return ans; } private int dfs(int[][] grid, int i, int j) { if (i < 0 || i == grid.length || j < 0 || j == grid.length) return 0; if (grid[i][j] == 0) return 0; int caughtFish = grid[i][j]; grid[i][j] = 0; // Mark 0 as visited return caughtFish + // dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + // dfs(grid, i, j + 1) + dfs(grid, i, j - 1); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution: def findMaxFish(self, grid: List[List[int]]) -> int: def dfs(i: int, j: int) -> int: if i < 0 or i == len(grid) or j < 0 or j == len(grid[0]): return 0 if grid[i][j] == 0: return 0 caughtFish = grid[i][j] grid[i][j] = 0 # Mark 0 as visited return caughtFish + \ dfs(i + 1, j) + dfs(i - 1, j) + \ dfs(i, j + 1) + dfs(i, j - 1) return max(dfs(i, j) for i in range(len(grid)) for j in range(len(grid[0])))