最大人工岛

发表于 | 分类于 |
字数统计: 623 | 阅读时长 ≈ 3

最大人工岛

在二维地图上， 0代表海洋， 1代表陆地，我们最多只能将一格 0 海洋变成 1变成陆地。

进行填海之后，地图上最大的岛屿面积是多少？（上、下、左、右四个方向相连的 1 可形成岛屿）

Input：

每个样例

第一行输入两个数字n m 表示地图的行数和列数。
后面n行每行输入m个数字，表示地图。

Output:

输出一个数字，表示将一格海洋变成陆地后最大的岛屿面积。

Sample Input:

2 2

1 0

0 1

2 2

1 1

1 0

2 2

1 1

1 1

Sample Output:

3

4

4 

(1) 思路：

遍历每一块海洋，让其变为陆地，加上附近大陆的面积。 这里的难点就是如何快速通过每一个陆地，得到这块大陆的面积。这里就可以用并查集来做。

(2) 代码：

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
#include<iostream>
#include<set>
#define MAXN 100
using namespace std;
int n,m,ans;
int map[MAXN][MAXN];
int tree[MAXN][2];
int direction[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};

int findroot(int x){
    if(tree[x][0]==-1){
        return x;
    }else{
        int root = findroot(tree[x][0]);
        tree[x][0] = root;
        return root;
    }
}

void uni(int x,int y){
    int root1 = findroot(x);
    int root2 = findroot(y);
    if(root1 == root2){
        return;
    }
    tree[root1][0]=root2;
    tree[root2][1]+=tree[root1][1];
    ans = max(ans,tree[root2][1]);
}
int main(){
    while(cin>>n>>m&&n!=0&&m!=0){
        ans=0;
        for(int i=0;i<n*m;i++){
            tree[i][0]=-1;
            tree[i][1]=1;
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>map[i][j];
            }
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(map[i][j]==1){
                    ans = max(ans,1);
                    for(int k=0;k<4;k++){
                        int I = i+direction[k][0];
                        int J = j+direction[k][1];
                        if(I>=0&&I<n&&J>=0&&J<m&&map[I][J]==1){
                            uni(I*m+J,i*m+j);
                        }
                    }
                }
            }
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(map[i][j]==0){
                    int size=1;
                    set<int> neb;
                    for(int k=0;k<4;k++){
                        int I=i+direction[k][0];
                        int J=j+direction[k][1];
                        if(I>=0&&I<n&&J>=0&&j<m&&map[I][J]==1){
                            int fa = findroot(I*m+J);
                            if(neb.count(fa)==0){
                                size+=tree[fa][1];
                                neb.insert(fa);
                            }
                        }
                    }
                    ans = max(ans,size);
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

0%