Maximum Number of Fish in a Grid

My algorithm just iterates through each individual cell and runs breadth-first search if the cell is a water cell (grid[r][c] > 0).

The BFS algorithm is as follows:

1. initialize ans and do ans += grid[r][c]
2. make grid[r][c] = 0 (so we do not visit grid[r][c] again)
3. recursively run BFS on all neighbouring cells (r, c+1), (r, c-1), (r+1, c) or (r-1, c) if they exist and are water cells, and then add the value that they return to ans
4. return ans

Then, we all we need to do is compute the maximum ans value that we have seen.

code

class Solution {
private:
    int bfs(vector<vector<int>> &grid, int i, int j) {
        int ans = grid[i][j];
        grid[i][j] = 0;
        if (i > 0 && grid[i-1][j] != 0) {
            ans += bfs(grid, i-1, j);
        }
        if (i < grid.size()-1 && grid[i+1][j] != 0) {
            ans += bfs(grid, i+1, j);
        }
        if (j > 0 && grid[i][j-1] != 0) {
            ans += bfs(grid, i, j-1);
        }
        if (j < grid[0].size()-1 && grid[i][j+1] != 0) {
            ans += bfs(grid, i, j+1);
        }
        return ans;
    }
public:
    int findMaxFish(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    continue;
                } else {
                    ans = max(ans, bfs(grid, i, j));
                }
            }
        }
        return ans;
    }
};

complexity

• Time: O(n^2)
• Space: O(1) (since we use the input matrix to store our seen squares, else O(n^2))