# 827. Making A Large Island

### 827. Making A Large Island

1. 给定一张矩阵图
2. 如果两个点相邻且都为1，这两个点连通
3. 至多把一个0改为1，问最大的连通岛的面积是多大

• 看数据结构，横竖最大是50，整个图最多才2500个点，直接枚举所有的0，改成1之后做dfs判断连通图，都可以解决
• 两个连通岛其实是两个集合，如果将一个0改成1，意味着把上下左右所在的岛都合并在一个集合中，我们需要一个数据结构，既可以将集合合并，又可以判断某两个元素是否在同一个集合中，这种数据结构就是并查集

class Solution {
private class Set {

int[] s;
int[] num;
int r;
int c;

private Set(int r, int c) {
this.r = r;
this.c = c;
this.s = new int[r * c];
this.num = new int[r * c];
for (int i = 0;i < this.s.length;i++) {
this.s[i] = i;
this.num[i] = 1;
}
}

private int calIdx(int x, int y) {
return x * c + y;
}

private int find(int idx) {
if (this.s[idx] == idx) {
return idx;
} else {
return this.s[idx] = find(this.s[idx]);
}
}

private void merge(int x1, int y1, int x2, int y2) {
int p1 = find(calIdx(x1, y1));
int p2 = find(calIdx(x2, y2));
if (p1 != p2) {
this.s[p1] = p2;
this.num[p2] += this.num[p1];
}
}

}

public int largestIsland(int[][] grid) {
int[] dx = new int[]{0,0,1,-1};
int[] dy = new int[]{1,-1,0,0};
Set set = new Set(grid.length, grid[0].length);
for (int i = 0;i < grid.length;i++) {
for (int j = 0;j < grid[0].length;j++) {
if (grid[i][j] == 0) {
continue;
}
for (int k = 0;k < 4;k++) {
if (i + dx[k] < 0 || i + dx[k] >= grid.length) {
continue;
}
if (j + dy[k] < 0 || j + dy[k] >= grid[0].length) {
continue;
}
if (grid[i + dx[k]][j + dy[k]] == 0) {
continue;
}
set.merge(i, j, i + dx[k], j + dy[k]);
}
}
}

int max = 0;
for (int i = 0;i < grid.length;i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
continue;
}

HashSet<Integer> t = new HashSet<>();
for (int k = 0;k < 4;k++) {
if (i + dx[k] < 0 || i + dx[k] >= grid.length) {
continue;
}
if (j + dy[k] < 0 || j + dy[k] >= grid[0].length) {
continue;
}
if (grid[i + dx[k]][j + dy[k]] == 0) {
continue;
}

t.add(set.find(set.calIdx(i + dx[k], j + dy[k])));
}

int ret = 0;
for (Integer p: t) {
ret += set.num[p];
}
ret ++;
max = Math.max(ret, max);
}
}
if (max == 0) {
max = grid.length * grid[0].length;
}
return max;
}
}


apachecn/AiLearning