岛屿

总时间限制:: 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天的连通块个数。

样例输入

样例输出

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

逆向思维，先考虑岛屿全部最后一年时岛屿的情况，再将时间往前“退潮”，减少连通块的数量

不过好像会超时4个点

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 struct node
 8 {
 9     int x,y,h;
10 }H[9000000];
11 int cnt;
12 int n,m,t,sum;
13 int f[9000000],T[100000],ans[100000];
14 bool vis[9000000];
15 
16 int dx[4]={-1,1,0,0};
17 int dy[4]={0,0,-1,1};
18 
19 int find(int x)
20 {
21     while(f[x]!=x) x=f[x];
22     return x;
23 }
24 
25 bool cmp(node a,node b)
26 {
27     return a.h>b.h;
28 }
29 
30 int read()
31 {
32     int x=0;char ch=getchar();
33     while(ch<'0'||ch>'9')ch=getchar();
34     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
35     return x;
36 }
37 
38 int main()
39 {
40     int pos=0;
41     memset(vis,0,sizeof(vis));
42     n=read();m=read();
43     for(int i=0;i<n;i++)
44         for(int j=0;j<m;j++)
45         {
46             int x=read();
47             f[cnt]=cnt;
48             H[cnt++]=(node){i,j,x};
49         }
50     sort(H,H+cnt,cmp);
51     t=read();
52     for(int i=0;i<t;i++) T[i]=read();
53     for(int i=t-1;i>=0;i--)
54     {
55         for(int j=pos;j<cnt;j++)
56         {
57             int x=H[j].x,y=H[j].y,h=H[j].h;
58             if(h<=T[i]||vis[x*m+y]) {pos=j;break;}
59             sum++;
60             vis[x*m+y]=1;
61             for(int k=0;k<4;k++)
62             {
63                 int xx=x+dx[k],yy=y+dy[k];
64                 if(xx>=0&&xx<n&&yy>=0&&yy<m&&vis[xx*m+yy])
65                 {
66                     int a=find(x*m+y),b=find(xx*m+yy);
67                     if(a!=b)
68                     {
69                         f[b]=f[a];
70                         sum--;
71                     }
72                 }
73             }
74         }
75         ans[i]=sum;
76     }
77     for(int i=0;i<t;i++) printf("%d ",ans[i]);
78     return 0;
79 }