827. Making A Large Island

,

UnionFind

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class Solution {
    private static final int[][] DIRECTIONS_RIGHT_AND_DOWN = new int[][]{{0, 1}, {1, 0}};
    private static final int[][] DIRECTIONS = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    private static class UnionFind {
        private final int[] parent;
        private final int[] size;

        public UnionFind(int count) {
            this.parent = new int[count];
            for (int i = 0; i < count; i++) {
                this.parent[i] = i;
            }
            this.size = new int[count];
            Arrays.fill(this.size, 1);
        }

        public int getRoot(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]]; // path compression
                x = parent[x];
            }
            return x;
        }

        public void union(int x, int y) {
            int xRoot = getRoot(x);
            int yRoot = getRoot(y);
            if (xRoot == yRoot) {
                return;
            }

            parent[xRoot] = yRoot;
            size[yRoot] += size[xRoot];
        }
    }

    public int largestIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;

        UnionFind unionFind = new UnionFind(m * n);
        boolean allWater = true;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    allWater = false;
                    for (int[] direction : DIRECTIONS_RIGHT_AND_DOWN) {
                        int x = i + direction[0];
                        int y = j + direction[1];
                        if (x < m && y < n && grid[x][y] == 1) {
                            unionFind.union(getIndex(n, i, j), getIndex(n, x, y));
                        }
                    }
                }
            }
        }

        if (allWater) {
            return 1;
        }

        int maxArea = 1;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    maxArea = Math.max(maxArea, unionFind.size[unionFind.getRoot(getIndex(n, i, j))]);
                } else {
                    Set<Integer> landRootSet = new HashSet<>();
                    for (int[] direction : DIRECTIONS) {
                        int x = i + direction[0];
                        int y = j + direction[1];
                        if (isLegal(m, n, x, y) && grid[x][y] == 1) {
                            landRootSet.add(unionFind.getRoot(getIndex(n, x, y)));
                        }
                    }
                    int area = 1;
                    for (int landRoot : landRootSet) {
                        area += unionFind.size[landRoot];
                    }
                    maxArea = Math.max(maxArea, area);
                }
            }
        }

        return maxArea;
    }

    private int getIndex(int cols, int i, int j) {
        return i * cols + j;
    }

    private boolean isLegal(int m, int n, int i, int j) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
    private static final int[][] DIRECTIONS = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int largestIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;

        Map<Integer, Integer> landNumberToAreaMap = new HashMap<>();
        int landNumber = 2;
        int maxArea = 1; // 全是海洋时任意转换一个格子
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int area = dfs(grid, m, n, landNumber, i, j);
                    landNumberToAreaMap.put(landNumber, area);
                    maxArea = Math.max(maxArea, area);
                    landNumber++;
                }
            }
        }

        if (landNumberToAreaMap.isEmpty()) {
            // 此处剪枝，提前返回
            return maxArea;
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    Set<Integer> landNumberSet = new HashSet<>(); // 当前 0 可能靠近同一区域的不同节点，所以需要去重
                    for (int[] direction : DIRECTIONS) {
                        int x = i + direction[0];
                        int y = j + direction[1];
                        if (isLegal(m, n, x, y) && grid[x][y] != 0) {
                            landNumberSet.add(grid[x][y]);
                        }
                    }

                    int area = 1;
                    for (int number : landNumberSet) {
                        area += landNumberToAreaMap.get(number);
                    }
                    maxArea = Math.max(maxArea, area);
                }
            }
        }

        return maxArea;
    }

    private int dfs(int[][] grid, int m, int n, int landNumber, int i, int j) {
        if (!isLegal(m, n, i, j) || grid[i][j] != 1) {
            return 0;
        }

        grid[i][j] = landNumber;

        return 1 + dfs(grid, m, n, landNumber, i, j + 1) + dfs(grid, m, n, landNumber, i, j - 1) +
                dfs(grid, m, n, landNumber, i + 1, j) + dfs(grid, m, n, landNumber, i - 1, j);
    }

    private boolean isLegal(int m, int n, int i, int j) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }
}

References

827. Making A Large Island