827.最大人工岛

链接：827.最大人工岛
难度：Hard
标签：深度优先搜索、广度优先搜索、并查集、数组、矩阵
简介：给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。返回执行此操作后，grid 中最大的岛屿面积是多少？。

题解 1 - cpp

• 编辑时间：2022-09-18
• 执行用时：620ms
• 内存消耗：167.5MB
• 编程语言：cpp
• 解法介绍：uf 记录所有岛，对每个 0 位置进行尝试合并。

class UnionFind{
public:
    int n;
    vector<int> list;
    UnionFind(int n){
        this->n = n;
        list = vector<int>(n);
        for (int i = 0; i < n; i++) list[i] = i;
    }
    int find(int e) {
        if (list[e] == e) return e;
        return list[e] = find(list[e]);
    }
    void uni(int e1, int e2) {
        int p1 = find(e1), p2 = find(e2);
        if (p1 != p2) list[p1] = p2;
    }
};
int dirs[4][2] = {
    {0, 1}, {0, -1},
    {-1, 0}, {1, 0}
};
typedef pair<int, int> node;
class Solution {
public:
    int n;
    int largestIsland(vector<vector<int>>& grid) {
        n = grid.size();
        vector<node> list0;
        UnionFind uf(n * n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int idx = toIdx(i, j);
                if (grid[i][j] == 0) {
                    uf.list[idx] = -1;
                    list0.push_back(make_pair(i, j));
                } else {
                    for (int k = 0; k < 4; k++) {
                        int x = i + dirs[k][0], y = j + dirs[k][1];
                        if (x < 0 || x == n || y < 0 || y == n || grid[x][y] == 0) continue;
                        uf.uni(idx, toIdx(x, y));
                    }
                }
            }
        }
        unordered_map<int, int> m;
        int ans = 0;
        for (int i = 0; i < uf.n; i++) if (uf.list[i] != -1) ans = max(ans, ++m[uf.find(i)]);
        for (auto &item : list0) {
            unordered_set<int> s;
            for (int i = 0; i < 4; i++) {
                int x = item.first + dirs[i][0], y = item.second + dirs[i][1];
                if (x < 0 || x == n || y < 0 || y == n || grid[x][y] == 0) continue;
                s.insert(uf.find(toIdx(x, y)));
            }
            int sum = 1;
            for (auto &p : s) sum += m[p];
            ans = max(ans, sum);
        }
        return ans;
    }
    int toIdx(int x, int y) {
        return x * n + y;
    }
};