LeetCode 827. 最大人工岛(并查集,bfs)
原题链接
困难
作者:
我是java同学
,
2023-08-08 20:33:32
,
所有人可见
,
阅读 76
class Solution {
public:
int n, m;
vector<int> p, sz;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
//坐标变换,二维换一维
int get(int x, int y) {
return x * m + y;
}
int largestIsland(vector<vector<int>>& grid) {
n = grid.size(), m = grid[0].size();
for (int i = 0; i < n * m; i ++ )
p.push_back(i), sz.push_back(1);
//将初始相连的1的连通块相连
int res = 1;//当全部都是0时,不会进下面循环,可以任意转换一个1
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (grid[i][j]) {
int a = get(i, j);
for (int k = 0; k < 4; k ++ ) {
int x = i + dx[k], y = j + dy[k];
if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y]) {
int b = get(x, y);
if (find(a) != find(b)) {
sz[find(b)] += sz[find(a)];
p[find(a)] = find(b);
}
}
}
res = max(res, sz[find(a)]);
}
//枚举所有的0
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (!grid[i][j]) {
map<int, int> S;//存上下左右四个方向不同的连通块
for (int k = 0; k < 4; k ++ ) {
int x = i + dx[k], y = j + dy[k];
if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y]) {
int a = get(x, y);
S[find(a)] = sz[find(a)];//存入连通块的大小
}
}//找完0的四个方向,把所有不同的连通块累加起来
int s = 1;
for (auto [k, v]: S) s += v;
res = max(res, s);
}
return res;
}
};