publicintlargestIsland(int[][] grid) { intm= grid.length, n = grid[0].length;
UnionFindunionFind=newUnionFind(m * n); booleanallWater=true; for (inti=0; i < m; i++) { for (intj=0; j < n; j++) { if (grid[i][j] == 1) { allWater = false; for (int[] direction : DIRECTIONS_RIGHT_AND_DOWN) { intx= i + direction[0]; inty= j + direction[1]; if (x < m && y < n && grid[x][y] == 1) { unionFind.union(getIndex(n, i, j), getIndex(n, x, y)); } } } } }
if (allWater) { return1; }
intmaxArea=1;
for (inti=0; i < m; i++) { for (intj=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 = newHashSet<>(); for (int[] direction : DIRECTIONS) { intx= i + direction[0]; inty= j + direction[1]; if (isLegal(m, n, x, y) && grid[x][y] == 1) { landRootSet.add(unionFind.getRoot(getIndex(n, x, y))); } } intarea=1; for (int landRoot : landRootSet) { area += unionFind.size[landRoot]; } maxArea = Math.max(maxArea, area); } } }
return maxArea; }
privateintgetIndex(int cols, int i, int j) { return i * cols + j; }
privatebooleanisLegal(int m, int n, int i, int j) { return i >= 0 && i < m && j >= 0 && j < n; } }
publicintlargestIsland(int[][] grid) { intm= grid.length, n = grid[0].length;
Map<Integer, Integer> landNumberToAreaMap = newHashMap<>(); intlandNumber=2; intmaxArea=1; // 全是海洋时任意转换一个格子 for (inti=0; i < m; i++) { for (intj=0; j < n; j++) { if (grid[i][j] == 1) { intarea= dfs(grid, m, n, landNumber, i, j); landNumberToAreaMap.put(landNumber, area); maxArea = Math.max(maxArea, area); landNumber++; } } }
if (landNumberToAreaMap.isEmpty()) { // 此处剪枝,提前返回 return maxArea; }
for (inti=0; i < m; i++) { for (intj=0; j < n; j++) { if (grid[i][j] == 0) { Set<Integer> landNumberSet = newHashSet<>(); // 当前 0 可能靠近同一区域的不同节点,所以需要去重 for (int[] direction : DIRECTIONS) { intx= i + direction[0]; inty= j + direction[1]; if (isLegal(m, n, x, y) && grid[x][y] != 0) { landNumberSet.add(grid[x][y]); } }
intarea=1; for (int number : landNumberSet) { area += landNumberToAreaMap.get(number); } maxArea = Math.max(maxArea, area); } } }
return maxArea; }
privateintdfs(int[][] grid, int m, int n, int landNumber, int i, int j) { if (!isLegal(m, n, i, j) || grid[i][j] != 1) { return0; }
grid[i][j] = landNumber;
return1 + 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); }
privatebooleanisLegal(int m, int n, int i, int j) { return i >= 0 && i < m && j >= 0 && j < n; } }