a guest
Dec 29th, 2021
53
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Solution {
2.
3. static final int NO_COLOR = 0;
4.
5. int n;
6. int[][] grid;
7.
8. int[][] color;
9. Map<Integer, Integer> islandSizes;
10.
11. int[][] dirs = {
12. { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }
13. };
14.
15. public int largestIsland(int[][] grid) {
16.
17. // setup
18. this.n = grid.length;
19. this.grid = grid;
20.
21. color = new int[n][n];
22. islandSizes = new HashMap<>();
23.
24. int maxArea = 0;
25.
26. // find area and coloring
27. int colorId = 1;
28.
29. for (int r = 0; r < n; r++) {
30. for (int c = 0; c < n; c++) {
31.
32. if (grid[r][c] == 1 && color[r][c] == NO_COLOR) {
33.
34. int area = getMaxAreaAndColoring(r, c, colorId);
35. islandSizes.put(colorId, area);
36. colorId++;
37.
38. // record max area
39. maxArea = Math.max(maxArea, area);
40. }
41. }
42. }
43.
44. // find largest island can be created by changing one 0 cell to 1
45. for (int r = 0; r < n; r++) {
46. for (int c = 0; c < n; c++) {
47.
48. if (grid[r][c] == 0) {
49. int area = getMaxAreaOfIslandCanMake(r, c);
50. maxArea = Math.max(maxArea, area);
51. }
52. }
53. }
54.
55. return maxArea;
56. }
57.
58. int getMaxAreaAndColoring(int row, int col, int colorId) {
59.
60. Queue<int[]> queue = new LinkedList<>();
61. queue.offer(new int[] { row, col });
62.
63. color[row][col] = colorId;
64.
65. int area = 0;
66. while (!queue.isEmpty()) {
67. int[] at = queue.poll();
68. int r = at[0];
69. int c = at[1];
70.
71. area++;
72.
73. for (int[] neighbor : getNeighbors(r, c)) {
74. int rr = neighbor[0];
75. int cc = neighbor[1];
76.
77. if (grid[rr][cc] == 1 && color[rr][cc] == NO_COLOR) {
78. color[rr][cc] = colorId;
79.
80. queue.offer(new int[] { rr, cc });
81. }
82. }
83. }
84.
85. return area;
86. }
87.
88. int getMaxAreaOfIslandCanMake(int row, int col) {
89.
90. int area = 1;
91. Set<Integer> seenIds = new HashSet<>();
92.
93. for (int[] neighbor : getNeighbors(row, col)) {
94. int rr = neighbor[0];
95. int cc = neighbor[1];
96.
97. int colorId = color[rr][cc];
98.
99. if (colorId != NO_COLOR) {
100. if (!seenIds.contains(colorId)) {
101. area += islandSizes.get(colorId);
102. }
103.
105. }
106. }
107.
108. return area;
109. }
110.
111. List<int[]> getNeighbors(int row, int col) {
112.
113. List<int[]> ans = new ArrayList<>();
114.
115. for (int[] dir : dirs) {
116. int rr = row + dir[0];
117. int cc = col + dir[1];
118.
119. if (0 <= rr && rr < n && 0 <= cc && cc < n) {
120. ans.add(new int[] { rr, cc });
121. }
122. }
123.
124. return ans;
125. }
126. }