leetcode 2658. 网格图中鱼的最大数目

题目如下

数据范围

使用并查集来做这道题。
其实按照题目的意思就是让我们求每一个联通的水域可以捞到的最大权值。
我们可以从前往后遍历这个二维数组只需要判断前一个水域和上一个水域是否和当前的(i, j)联通如果有则合并水域，同时用一个weight数组保存每一个联通的大水域的总权值也就是能捞到的鱼数量。

通过代码

class bin {
public:vector<int> path;vector<int> weight;bin(int n) {//这个n是没有必要的 博主原以为n m是一样大的想省点内存 后来发现不一样也不想改了 太懒了。。。。 path.resize(n * n);//二维数组转成一维地址就是 i * m + j i是行 j 是列 m是列数weight.resize(n * n);for (int i = 0; i < n * n; i++) {weight[i] = -1;path[i] = i;}}int find(int target) {if (path[target] == target)return target;path[target] = find(path[target]);//路径压缩return path[target];}void unio(int a, int b) {int a1 = find(a);int b1 = find(b);if (a1 == b1)return;path[b1] = a1;weight[a1] += weight[b1];}int max_fish(int n) {//这个n是没有必要的 博主原以为n m是一样大的想省点内存 后来发现不一样也不想改了 太懒了。。。。 int max = 0;for (int i = 0; i < n * n; i++) {if (weight[i] > max)max = weight[i];}return max;}
};
class Solution {
public:int findMaxFish(vector<vector<int>>& grid) {int n = grid.size();int m = grid[0].size();bin b(10);for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {b.weight[i * m + j] = grid[i][j];}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] != 0) {if (j > 0 && grid[i][j - 1] != 0) {b.unio(i * m + j - 1, i * m + j);}if (i > 0 && grid[i - 1][j] != 0) {b.unio((i - 1) * m + j, i * m + j);}}}}return b.max_fish(10);}
};

tips:无论先判断上面的水域联通还是左边的水域联通都可以 只需要判断上面和左边的情况就行因为下面和右边总会遍历到。如果愿意从后往前遍历同理只需判断下面和右边情况就行。