827. maximum man-made island and collection search

827. The largest artificial island

Give you a size of  n x n  Binary matrix  grid . most   Only one grid  0  become  1 .

Return to... After performing this operation ,grid  What is the largest island area in the ？

Islands   By a group 、 Next 、 Left 、 Connected in four directions to the right  1  formation .

Example 1:

 Input : grid = [[1, 0], [0, 1]]
 Output : 3
 explain :  One grid 0 become 1, Finally, connecting the two islands, we get an area of  3  The island of .

Example 2:

 Input : grid = [[1, 1], [1, 0]]
 Output : 4
 explain :  One grid 0 become 1, The area of the island expanded to  4.

Example 3:

 Input : grid = [[1, 1], [1, 1]]
 Output : 4
 explain :  No, 0 Can make us become 1, The area is still  4.

Tips ：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 500
• grid[i][j]  by  0  or  1

  The result of doing the question

success , The problem is very simple if you know how to search the set

step

1. Initialize parent node , Root node size

2. For adjacent 1 Connect

3. Yes 0 Location handling , Connect up, down, left and right 4 Maximum value after block , Special , Count yourself 1

details

1. whole 1 Handle , return n*n

2. whole 0 Handle , return 1（ This step may not be handled ）

3. Consider the case where the upper, lower, left and right blocks are adjacent , De duplication for parent node

class Solution {
        int[] parent;
        int[] sizes;
        int n;
    public int largestIsland(int[][] grid) {
        n = grid.length;
        parent = new int[n*n];
        sizes = new int[n*n];
        boolean allZero = true;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                int v = flat(i,j);
                parent[v] = v;
                sizes[v] = grid[i][j];
                allZero = allZero && sizes[v]==0;
            }
        }

        if(allZero) return 1;

        int[] directions = new int[]{0,1,0,-1,0};
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j]!=1) continue;
                int t = flat(i,j);

                for(int k = 0; k < 4; k++){
                    int x = i+directions[k];
                    int y = j+directions[k+1];

                    if(x>=0&&x<n&&y>=0&&y<n&&grid[x][y]==1){
                        connect(t,flat(x,y));
                    }
                }
            }
        }

        if(sizes[root(0)]==n*n) return n*n;
        int ans = 0;
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j]==1) continue;
                int size = 1;
                Set<Integer> p = new HashSet<>();
                for(int k = 0; k < 4; k++) {
                    int x = i + directions[k];
                    int y = j + directions[k + 1];
                    if(x>=0&&x<n&&y>=0&&y<n && p.add(root(flat(x,y)))){
                        size += sizes[root(flat(x,y))];
                    }
                }
                ans = Math.max(size,ans);
            }
        }

        return ans;
    }

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

    public void connect(int a, int b){
        int rootA = root(a);
        int rootB = root(b);
        if(rootA == rootB) return;
        if(sizes[rootA]>sizes[rootB]){
            sizes[rootA]+=sizes[rootB];
            parent[rootB] = rootA;
        }else{
            sizes[rootB]+=sizes[rootA];
            parent[rootA] = rootB;
        }
    }

    private int root(int v){
        while (parent[v]!=v){
            parent[v] = parent[parent[v]];
            v = parent[v];
        }
        return v;
    }
}