题目简介：
给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
返回执行此操作后，grid 中最大的岛屿面积是多少？
岛屿 由一组上、下、左、右四个方向相连的 1 形成。
示例 1:
1
2
3
| 输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
|
示例 2:
1
2
3
| 输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。
|
示例 3:
1
2
3
| 输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。
|
提示：
n == grid.lengthn == grid[i].length1 <= n <= 500grid[i][j] 为 0 或 1
思路：
我们首先需要判断哪些岛屿是连在一起的，也就是有多少个1是连在一起的，所以使用并查集。
第一轮遍历，我们将连在一起的岛屿判断出来，并记录覆盖的最大面积。
第二轮遍历，我们观察每个0四周是否有1，并计算合并之后的面积（注意去除重复覆盖的面积，利用set, 最后更新最大面积即可。
代码如下：
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
| class Solution {
public:
int find(int x, vector<int>& p){
if(p[x] != x)
p[x] = find(p[x], p);
return p[x];
}
int largestIsland(vector<vector<int>>& grid) {
vector<int> x_dir = {0, 1, 0, -1};
vector<int> y_dir= {-1, 0, 1, 0};
int n = grid.size();
vector<int> p(n * n);
iota(p.begin(), p.end(), 0);
vector<int> map_area(n * n, 1);
int res = 1;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(grid[i][j]){
for(int k = 0; k < 4; k++){
int x = i + x_dir[k];
int y = j + y_dir[k];
if(x < 0 || x >= n || y < 0 || y >= n || !grid[x][y])
continue;
int item1 = find(x * n + y, p);
int item2 = find(i * n + j, p);
if(item1 != item2){
p[item1] = item2;
map_area[item2] += map_area[item1];
res = max(res, map_area[item2]);
}
}
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
int now_size = 1;
unordered_set<int> vis;
if(!grid[i][j]){
for(int k = 0; k < 4; k++){
int x = i + x_dir[k];
int y = j + y_dir[k];
if(x < 0 || x >= n || y < 0 || y >= n || !grid[x][y])
continue;
int item = find(x * n + y, p);
if(!vis.count(item)){
now_size += map_area[item];
vis.insert(item);
res = max(res, now_size);
}
}
}
}
}
return res;
}
};
|
