关于算法:每日一题最大人工岛

827. 最大人工岛

关键词：深度优先、并查集、枚举

题目起源：827. 最大人工岛 – 力扣（Leetcode）

题目形容

 T 深度优先
 T 并查集
 T 枚举 

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

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

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

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

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

 输出: grid = [[1, 1], [1, 1]]
输入: 4
解释: 没有 0 能够让咱们变成 1，面积仍然为 4。

 数据范畴
n == grid.length
n == grid[i].length
1 <= n <= 500
grid[i][j] 为 0 或 1

问题剖析

连通块问题可应用深搜来打标记，也能够应用并查集来保护，以下就采纳并查集来解决本题。

首先遍历一遍矩阵，当相邻两格均为岛屿时，认为二者连通，用并查集来保护二者的连通性。

枚举每一个网格的翻转（前提是能翻转），将其退出图中，其是否能使得其上下左右的连通块（或其中几个）相连，留神相似于上方连通块与左方连通块原本就相连的状况。

工夫复杂度：O(n^2)，find 函数的工夫可认为是 O(1) 的。

空间复杂度：O(n^2)

代码实现

const int N = 25e4 + 5;
int p[N], size[N], n;

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

/**
 * 将二维坐标映射到一维
 */
int pos(int x, int y) {return x * n + y;}

int largestIsland(vector<vector<int>> &grid) {n = grid.size();

    // 并查集初始化
    for (int i = 0, k = n * n; i < k; i++) {p[i] = i, size[i] = 1;
    }

    // 后果
    int res = grid[0][0];   // 当 n 为 1 时的非凡状况

    // 独自解决第一行和第一列
    for (int i = 1, pa, pb; i < n; i++) {if (grid[0][i] && grid[0][i - 1]) {pa = find(pos(0, i)), pb = find(pos(0, i - 1));
            p[pa] = pb, size[pb] += size[pa];
            res = max(size[pb], res);       // 单个连通块最大值
        }
        if (grid[i][0] && grid[i - 1][0]) {pa = find(pos(i, 0)), pb = find(pos(i - 1, 0));
            p[pa] = pb, size[pb] += size[pa];
            res = max(size[pb], res);       // 单个连通块最大值
        }
    }

    // 处于其余块的连通性
    for (int i = 1, pa, pb; i < n; i++) {for (int j = 1; j < n; j++) {if (!grid[i][j])continue;
            pa = find(pos(i, j));
            if (grid[i - 1][j]) {pb = find(pos(i - 1, j));
                if (pa != pb) {p[pb] = pa, size[pa] += size[pb];
                }
            }
            if (grid[i][j - 1]) {pb = find(pos(i, j - 1));
                if (pa != pb) {p[pb] = pa, size[pa] += size[pb];
                }
            }
            res = max(size[pa], res);       // 单个连通块最大值
        }
    }

    // 枚举每个翻转
    for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (grid[i][j])continue;
            
            // 以后网格连同上下左右连通块的和
            int tp = 1;
            
            // 上下左右四个方向的连通块的根节点（代表结点）int up = -1, dn = -1, lt = -1, rt = -1;
            
            if (i - 1 >= 0 && grid[i - 1][j]) {up = find(pos(i - 1, j));   // 记录上方连通块的根节点
                tp += size[up];                     // 累加上方连通块的大小
            }
            if (i + 1 < n && grid[i + 1][j]) {dn = find(pos(i + 1, j));
                if (dn != up) {             // 下方连通块不与上方连通块连通
                    tp += size[dn];
                }
            }
            if (j - 1 >= 0 && grid[i][j - 1]) {lt = find(pos(i, j - 1));
                if (lt != up && lt != dn) { // 左侧连通块不与上、下方连通块连通
                    tp += size[lt];
                }
            }
            if (j + 1 < n && grid[i][j + 1]) {rt = find(pos(i, j + 1));
                if (rt != up && rt != dn && rt != lt) { // 右侧连通块不与上、下、左方连通块连通
                    tp += size[rt];
                }
            }

            // 取最大值
            res = max(tp, res);
        }
    }
    return res;
}