Today I have done leetcode's January LeetCoding Challenge with cpp.

January LeetCoding Challenge 28

Description

Maximum Number of Fish in a Grid

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

Solution

struct UnionSet {
  vector<int> parent;
  vector<int> count;
public:
  UnionSet(int size): parent(size), count(size) {
    iota(parent.begin(), parent.end(), 0);
  }

  void setCount(int key, int val) {
    count[key] = val;
  }

  int getCount(int key) {
    return count[key];
  }

  int find(int x) {
    if(parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
  }

  void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if(y != parent[x]) count[y] += count[x];
    parent[x] = y;
  }
};
class Solution {
public:
  int findMaxFish(vector<vector<int>>& grid) {
    int rows = grid.size();
    int cols = grid.front().size();
    UnionSet us(rows * cols);
    for(int r = 0; r < rows; ++r) {
      for(int c = 0; c < cols; ++c) {
        us.setCount(r * cols + c, grid[r][c]);
      }
    }
    for(int r = 0; r < rows; ++r) {
      for(int c = 0; c < cols; ++c) {
        if(!grid[r][c]) continue;
        if(r != rows - 1 && grid[r + 1][c]) us.merge(r * cols + c, r * cols + c + cols);
        if(c != cols - 1 && grid[r][c + 1]) us.merge(r * cols + c, r * cols + c + 1);
      }
    }
    int answer = 0;
    for(int i = 0; i < rows * cols; ++i) {
      answer = max(answer, us.getCount(i));
    }
    return answer;
  }
};

// Accepted
// 3842/3842 cases passed (11 ms)
// Your runtime beats 51.14 % of cpp submissions
// Your memory usage beats 68.65 % of cpp submissions (96.1 MB)