827. 最大人工岛
难度困难83
在二维地图上， 0代表海洋， 1代表陆地，我们最多只能将一格 0 海洋变成 1变成陆地。
进行填海之后，地图上最大的岛屿面积是多少？（上、下、左、右四个方向相连的 1 可形成岛屿）
示例 1:
输入: [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
示例 2:
输入: [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。
示例 3:
输入: [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。
说明:
1 <= grid.length = grid[0].length <= 500 <= grid[i][j] <= 1
假hard题。搜一遍每个连通块的大小，同时求出来每个点所属的连通块的编号。然后遍历每个0，把其邻接的上下左右四个点所属的连通块（注意编号相同的连通块只能算一个，可以用set去重）的大小加起来再加上1然后用这个值更新答案即可。注意数据范围得开大一点，50的上界貌似是假的。
class Solution {
public:
int n, a[550][550];
int cnt = 0, belong[550][550];//块个数，所属联通块编号
int sz[550 * 550];//块大小
int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int maxx = 0;
void dfs(int x, int y, int id) {
belong[x][y] = id;
sz[id]++;//当前块大小++
maxx = max(maxx, sz[id]);
for(int i = 0; i < 4; i++) {
int nx = x + d[i][0], ny = y + d[i][1];
if(belong[nx][ny] || nx > n || nx < 1 || ny > n || ny < 1 || a[nx][ny] == 0) continue;
dfs(nx, ny, id);
}
}
int largestIsland(vector<vector<int>>& grid) {
n = grid.size();
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
a[i + 1][j + 1] = grid[i][j];
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(a[i][j] == 1 && !belong[i][j]) {
cnt++;
dfs(i, j, cnt);
}
}
}
int ans = 0;
for(int x = 1; x <= n; x++) {
for(int y = 1; y <= n; y++) {
if(a[x][y] == 1) continue;
int tmp_ans = 0;
set<int> s;
for(int k = 0; k < 4; k++) {
int nx = x + d[k][0], ny = y + d[k][1];
if(nx > n || nx < 1 || ny > n || ny < 1 || a[nx][ny] == 0 || s.find(belong[nx][ny]) != s.end()) continue;
tmp_ans += sz[belong[nx][ny]];
s.insert(belong[nx][ny]);
}
ans = max(ans, tmp_ans + 1);//别忘记加上反转后的
}
}
ans = max(ans, maxx);
return ans;
}
};