827.最大人工岛.md

827.最大人工岛

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

 

示例 1:

输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。

示例 2:

输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。

示例 3:

输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。

 

提示：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 500
• grid[i][j] 为 0 或 1

标签：

['深度优先搜索', '广度优先搜索', '并查集', '数组', '矩阵']

难度：Hard

喜欢：178

---

并查集

算法思路

• 并查集 标记每个岛屿，开一个数组记录岛屿大小（合并时需要注意顺序，我一般习惯是把大坐标合并到小坐标）
• 遍历矩阵，判断向右、向下 两种方式可以合并得到的人工岛面积最大值
  • 两个位置 间隔 $1$，且不属于同一岛屿（不在同一集合）

时间复杂度 $O(n^2log{n^2})$

代码实现

class Solution {


public:
    static const int N = 250010;

    int f[N];
    int cnt[N];
    int n;

    int dx[2] = {0, 1}, dy[2] = {1, 0};
    int dxx[4] = {-1, 0, 1, 0}, dyy[4] = {0, 1, 0, -1};

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

    void merge(int x, int y) { // 小坐标 做 更高的父节点
        int p = find(x), q = find(y);
        if (p == q) return;
        if (p > q) {
            f[p] = q; // 大坐标 合并到 小坐标
            cnt[q] += cnt[p];
        } else merge(q, p);
    }

    int get(int x, int y) {
        return x * n + y;
    }

    int largestIsland(vector<vector<int>> &g) {
        n = g.size();
        for (int i = 0; i < N; ++i) {
            f[i] = i;
            cnt[i] = 1;
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (g[i][j] == 0) continue;
                for (int k = 0; k < 2; ++k) {
                    int x = dx[k] + i, y = dy[k] + j;
                    if (x < 0 || x >= n || y < 0 || y >= n) continue;
                    if (g[x][y] == 0) continue;

                    merge(get(i, j), get(x, y));
                }
            }
        }

        int res = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (g[i][j] == 1) {
                    res = max(res, cnt[get(i, j)]);
                    continue;
                }
                int sum = 1;
                unordered_set<int> st;
                for (int k = 0; k < 4; ++k) {
                    int x = dxx[k] + i, y = dyy[k] + j;
                    if (x < 0 || x >= n || y < 0 || y >= n) continue;
                    if (g[x][y] == 0) continue;
                    int p = find(get(x, y));
                    if (st.count(p)) continue;
                    sum += cnt[p];
                    st.insert(p);
                }
                res = max(res, sum);
            }
        }
        return res;
    }
};

参考文献