OpenJudge 东方14ACM小组 / 20170123 02 岛屿

总时间限制: 

40000ms

 

单个测试点时间限制: 

4000ms

 

内存限制: 

128000kB

描述

从前有一座岛屿，这座岛屿是一个长方形，被划为N*M的方格区域，每个区域都有一个确定的高度。不幸的是海平面开始上涨，在第i年，海平面的高度为t[i]。如果一个区域的高度小于等于海平面高度，则视为被淹没。那些没有被淹没的连通的区域够成一个连通块。现在问第i年，这样的连通块有多少个。

    例如：第一年海平面高度为1，有2个连通块。

                      第二年海平面高度为2，有3个连通块。

 

输入

第一行包含两个数N,M。
接下来是一个N*M的矩阵，第i行第j列表示这个格子的高度h[i][j]
接下来是一个数T，表示有T天，
最后一行有T个数，第i个数表示第i天的水位高度。（保证是递增的）

输出

输出包含一行T个数，第i个数表示第i天的连通块个数。

样例输入

4 5
1 2 3 3 1
1 3 2 2 1
2 1 3 4 3
1 2 2 2 2
5
1 2 3 4 5

样例输出

2 3 1 0 0

提示

对于50%的数据： 1 <= n*m <= 1000, 1<= T <=3000
对于100%的数据：1<= n <= 3000 , 1<= m <= 3000 , 1<=T<=100000 
1<= h[i][j] <=10^9

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm> 
 5 using namespace std;
 6 int t[100010],ans[100010],f[9000010],n,m,tot,si; 
 7 struct node{
 8     int x,y,high;
 9 }a[9000010];
10 bool vis[9000010];
11 int cmp(node i,node j){return i.high>j.high;}
12 int dx[]={0,0,1,-1};
13 int dy[]={-1,1,0,0};
14 int find(int x){
15     if(x==f[x]) return x;
16     else return f[x]=find(f[x]);
17 }
18 void solve(){
19     int sum=0,pos=1;
20     sort(a+1,a+tot+1,cmp);
21     for(int p=si;p>=1;p--){
22         for(int i=pos;i<=tot;i++){
23             int h=a[i].high,x=a[i].x,y=a[i].y;
24             if(h<=t[p]){ pos=i;break; }
25             if(h>t[p]&&!vis[(x-1)*m+y]) {
26                 sum++;vis[(x-1)*m+y]=true;
27                 for(int j=0;j<4;j++){
28                     int nx=x+dx[j],ny=y+dy[j];
29                     int k1=find((nx-1)*m+ny),
30                         k2=find((x-1)*m+y);
31                     if(nx>0&&nx<=n&&ny>0&&ny<=m
32                       &&vis[k1]&&k1!=k2){
33                           sum--;f[k1]=k2;
34                       }
35                 }
36             }
37         }
38         ans[p]=sum;
39     }
40     for(int i=1;i<=si;i++) printf("%d ",ans[i]);
41 }
42 int main()
43 {
44     scanf("%d%d",&n,&m);
45     for(int i=1;i<=n;i++)
46       for(int j=1;j<=m;j++){
47           scanf("%d",&a[++tot].high);
48           a[tot].x=i;a[tot].y=j;
49       }
50     for(int i=1;i<=tot;i++) f[i]=i;
51     scanf("%d",&si);
52     for(int i=1;i<=si;i++) scanf("%d",&t[i]);
53     solve();
54     return 0;
55 }

神一样的倒序并查集。。。。

OpenJudge 东方14ACM小组 / 20170123 02 岛屿

原文：http://www.cnblogs.com/suishiguang/p/6344791.html