题目描述

文字版

代码

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);

        int res = 0;
        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)]);
                }

        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                // 填海
                if (!grid[i][j]) {
                    map<int, int> hash;
                    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);
                            // 填海后上下左右的数量
                            hash[find(a)] = sz[find(a)];
                        }
                    }
                    // 填海的个数 最少是1
                    int s = 1;
                    for (auto [k, v]: hash) s += v;
                    // 填海的最大值
                    res = max(res, s);
                }
        return res;
    }
};