2658

2658. Maximum Number of Fish in a Grid (Medium)

You are given a 0-indexed 2D matrix grid of size m x n, where (r, c) represents:

• A land cell if grid[r][c] = 0, or
• A water cell containing grid[r][c] fish, if grid[r][c] > 0.

A fisher can start at any water cell (r, c) and can do the following operations any number of times:

• Catch all the fish at cell (r, c), or
• Move to any adjacent water cell.

Return the maximum number of fish the fisher can catch if he chooses his starting cell optimally, or 0 if no water cell exists.

An adjacent cell of the cell (r, c), is one of the cells (r, c + 1), (r, c - 1), (r + 1, c) or (r - 1, c) if it exists.

 

Example 1:

Input: grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
Output: 7
Explanation: The fisher can start at cell (1,3) and collect 3 fish, then move to cell (2,3) and collect 4 fish.

Example 2:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
Output: 1
Explanation: The fisher can start at cells (0,0) or (3,3) and collect a single fish. 

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• 0 <= grid[i][j] <= 10

Companies: Adobe

Related Topics:
Array, Depth-First Search, Breadth-First Search, Union Find, Matrix

Similar Questions:

• Number of Islands (Medium)

Solution 1. Union Find

// OJ: https://leetcode.com/problems/maximum-number-of-fish-in-a-grid
// Author: github.com/lzl124631x
// Time: O(MNlogMN)
// Space: O(MN)
class UnionFind {
    vector<int> id;
public:
    UnionFind(int n) : id(n) {
        iota(begin(id), end(id), 0);
    }
    int find(int a) {
        return id[a] == a ? a : (id[a] = find(id[a]));
    }
    void connect(int a, int b) {
        id[find(a)] = find(b);
    }
};
class Solution {
public:
    int findMaxFish(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size(), dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}, ans = 0;
        UnionFind uf(M * N);
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == 0) continue;
                for (auto &[dx, dy] : dirs) {
                    int a = i + dx, b = j + dy;
                    if (a < 0 || a >= M || b < 0 || b >= N || A[a][b] == 0) continue;
                    uf.connect(i * N + j, a * N + b);
                }
            }
        }
        unordered_map<int, int> m;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == 0) continue;
                ans = max(ans, m[uf.find(i * N + j)] += A[i][j]);
            }
        }
        return ans;
    }
};