leetcode-827：最大人工岛

题目

题目连接

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

示例 1:

输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
1
2
3

示例 2:

输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。
1
2
3

示例 3:

输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。
1
2
3

解题

方法一：dfs+map+枚举变化点

通过map记录每个岛屿对应的面积
通过不同值去标记不同的岛屿。

然后遍历矩阵，尝试让0变成1，然后查看最大面积

class Solution {
public:
    vector<vector<int>> dirs={{-1,0},{1,0},{0,-1},{0,1}};
    void dfs(unordered_map<int,int>& mp,vector<vector<int>>& grid,int id,int x,int y,int& area){
        grid[x][y]=id;
        area++;
        for(vector<int>& dir:dirs){
            int nx=x+dir[0];
            int ny=y+dir[1];
            if(nx<0||nx>=grid.size()||ny<0||ny>=grid.size()||grid[nx][ny]!=1) continue;
            dfs(mp,grid,id,nx,ny,area);
        }
    }

    int largestIsland(vector<vector<int>>& grid) {
        int n=grid.size();
        int id=-1;
        unordered_map<int,int> mp;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]!=1) continue;
                int area=0;
                dfs(mp,grid,id,i,j,area);
                mp[id]=area;
                id--;
                
            }
        }

        int res=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==0){
                    unordered_set<int> set;
                    int cur=1;
                    for(vector<int>& dir:dirs){
                        int nx=i+dir[0];
                        int ny=j+dir[1];
                        if(nx<0||nx>=n||ny<0||ny>=n||grid[nx][ny]==0) continue;
                        if(!set.count(grid[nx][ny])){
                            cur+=mp[grid[nx][ny]];
                            set.insert(grid[nx][ny]);
                        }
                    }
                    res=max(res,cur);
                }
            }
        }
        return res==0?n*n:res;//全1的情况下res不会进行更新。 只要有0, res至少为1
    }
};
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

方法二：并查集+枚举

查并集，可以查看每个集合中元素的数量
第一次遍历，将相邻的陆地加入到一个集合中
第二次遍历，如何相邻岛屿，那么就将它们岛屿的面积（集合的大小）加起来，注意去重。

class UnionFind{
public:
    vector<int> parent;
    vector<int> size;
    UnionFind(int n){
        parent.resize(n*n);
        size.resize(n*n,1);
        iota(parent.begin(),parent.end(),0);
    }
    int find(int index){
        if(index==parent[index]) return index;
        return parent[index]=find(parent[index]);
    }
    void unite(int index1,int index2){
        int p1=find(index1),p2=find(index2);
        parent[p1]=p2;
        if(p1!=p2){//如果相等,会出现把size[p1]=size[p2]=0 都清空
            size[p2]+=size[p1];
            size[p1]=0;
        }
    }
    int getSize(int index){
        return size[find(index)];
    }
};

class Solution {
public:
    vector<vector<int>> dirs={{-1,0},{0,-1},{1,0},{0,1}};
    int largestIsland(vector<vector<int>>& grid) {
        int n=grid.size();
        UnionFind uf(n);
        int res=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    for(int k=0;k<2;k++){
                        vector<int>& dir=dirs[k];
                        int nx=i+dir[0];
                        int ny=j+dir[1];
                        if(nx<0||nx>=n||ny<0||ny>=n||grid[nx][ny]==0) continue;
                        uf.unite(nx*n+ny,i*n+j);
                    }
                    res=max(res,uf.getSize(i*n+j));
                }
            }
        }
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==0){
                    int cur=1;
                    unordered_set<int> set;
                    for(vector<int>& dir:dirs){
                        int nx=i+dir[0];
                        int ny=j+dir[1];
                        if(nx<0||nx>=n||ny<0||ny>=n||grid[nx][ny]==0) continue;
                        int p=uf.find(nx*n+ny);
                        if(!set.count(p)){
                            cur+=uf.getSize(p);
                            set.insert(p);
                        }
                    }
                    res=max(cur,res);
                }
            }
        }
        return res;
    }
};
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