Leetcode--Java--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。

并查集
整体思路：先确定所有的连通块，然后看是否变成1能够扩大连通块。

1. 先初始化并查集，记录以每个1的岛屿所在的连通块个数。涉及到将岛屿二维坐标转化为并查集中一维坐标。（ 乘所有列数+ 所在列数）。
2. 合并相连的，就是合并并查集。以一个1岛屿为起点，向四周探寻进行合并，同时在过程中记录最大的岛屿面积。
3. 寻找水0进行修改，探索四周如果有岛屿1，就能合并起来。这里要注意去重，由于四周的1可能本身就是一个连起来的（要用set去重，就是将公共祖先丢入并查集），最后将set里面的岛屿所在连通块个数相加就是最终面积，不要0改变后本身多了个1。

class Solution { 
    int m, n;
    int size[], p[];
    //并查集，查找祖先
    public int find(int x) {
          if (p[x] != x) {
              p[x] = find(p[x]);
          }
          return p[x];
    }
    //二维坐标转一维
    public int get(int x, int y) {
        return x * n + y;
    }

    public int largestIsland(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        size = new int[m * n];
        p = new int[m * n];
        int dx[] = new int[]{1, 0, -1, 0};
        int dy[] = new int[]{0, 1, 0, -1};
        //初始化并查集
        for (int i = 0; i < m * n; i ++ ) {
            p[i] = i;
        }
        int maxResult = 0;
        //初始化各个岛屿
        for (int i = 0; i < m; i ++ ) {
            for (int j = 0; j < n; j ++ ) {
                //是岛屿的情况下
                if (grid[i][j] == 1) {
               size[get(i, j)] = 1;
               maxResult = 1;
                }
            }
        }
        //合并岛屿 （并查集的合并部分）
        for (int i = 0; i < m; i ++ ) {
            for (int j = 0; j < n; j ++ ) {
                //是岛屿的情况下
                if (grid[i][j] == 1) {
                    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 >= m || y < 0 || y >= n || grid[x][y] == 0) continue;
                        int b = get(x, y);
                        int fa = find(a);
                        int fb = find(b);
                        if (fa != fb) {
                            p[fb] = fa;
                            size[fa] += size[fb];
                            maxResult = Math.max(maxResult, size[fa]);
                        }
                    }
                }
            }
        } 
        //全是0的话，随便改一个
        if (maxResult == 0) return 1;
          //改0为1，再进行合并岛屿
        for (int i = 0; i < m; i ++ ) {
            for (int j = 0; j < n; j ++ ) {
                if (grid[i][j] == 1) continue;
                Set set = new HashSet<>();
                for (int k = 0; k < 4; k ++ ) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) continue;
                    set.add(find(get(x, y)));
                }
                int sum = 0;
                for (int s: set) {
                    sum += size[s];
                }   
                //加一是加上改变的那个0
                maxResult = Math.max(maxResult, sum + 1);
            }
        }
       return maxResult;
    }
}