Coconuts HDU - 5925 (二维离散化求连通块的个数以及大小)
题目链接：
D - Coconuts
HDU - 5925
题目大意：首先是T组测试样例，然后给你n*m的矩阵，原先矩阵里面都是白色的点，然后再输入k个黑色的点。这k个黑色的点可能会使得原先白色的点分成多个联通块，然后问你白色联通块的个数和每一个连通块里面白色的点的个数。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。具体思路：输入的点坐标比较大，但是个数比较小，所以离散化坐标就可以了。标记每一个整块里面的白色的点的个数就可以了。
AC代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 # define ll long long 4 # define inf 0x3f3f3f3f 5 const int maxn = 2e5+100; 6 const int maxm =400+100; 7 vector<ll>contx; 8 vector<ll>conty;// 注意开long long 9 int vis[maxm<<2][maxm<<2]; 10 ll a[maxm<<2],cnt; 11 ll Map[maxm<<2][maxm<<2]; 12 int f[2][4]= {{1,-1,0,0},{0,0,1,-1}}; 13 struct node 14 { 15 int x,y; 16 node() {} 17 node(int xx,int yy) 18 { 19 x=xx; 20 y=yy; 21 } 22 } q[maxn]; 23 bool judge(int x,int y) 24 { 25 if(x>=1&&y>=1&&x<=contx.size()&&y<=conty.size()) 26 return true; 27 return false; 28 } 29 void dfs(int x,int y) 30 { 31 cnt+=Map[x][y]; 32 vis[x][y]=1; 33 for(int i=0; i<4; i++) 34 { 35 int tx=x+f[0][i]; 36 int ty=y+f[1][i]; 37 if(judge(tx,ty)&&vis[tx][ty]==0) 38 dfs(tx,ty); 39 } 40 } 41 int main() 42 { 43 int T,Case=0; 44 scanf("%d",&T); 45 while(T--) 46 { 47 int n,m,tot; 48 scanf("%d %d",&n,&m); 49 memset(vis,0,sizeof(vis)); 50 memset(Map,0,sizeof(Map)); 51 contx.clear(); 52 conty.clear(); 53 scanf("%d",&tot); 54 contx.push_back(1); 55 conty.push_back(1); 56 contx.push_back(n); 57 conty.push_back(m); /// 先把四个角输进去 58 for(int i=1; i<=tot; i++) 59 { 60 scanf("%d %d",&q[i].x,&q[i].y); 61 contx.push_back(q[i].x); 62 conty.push_back(q[i].y); 63 if(q[i].x-1>=1) 64 contx.push_back(q[i].x-1); 65 if(q[i].x+1<=n) 66 contx.push_back(q[i].x+1); 67 if(q[i].y-1>=1) 68 conty.push_back(q[i].y-1); 69 if(q[i].y+1<=m) 70 conty.push_back(q[i].y+1); 71 } 72 sort(contx.begin(),contx.end()); 73 sort(conty.begin(),conty.end()); 74 contx.erase(unique(contx.begin(),contx.end()),contx.end()); 75 conty.erase(unique(conty.begin(),conty.end()),conty.end()); 76 for(int i=1; i<=tot; i++) 77 { 78 int t1=lower_bound(contx.begin(),contx.end(),q[i].x)-contx.begin()+1; 79 int t2=lower_bound(conty.begin(),conty.end(),q[i].y)-conty.begin()+1; 80 vis[t1][t2]=1; 81 } 82 for(int i=0; i<contx.size(); i++) 83 { 84 for(int j=0; j<conty.size(); j++) 85 { 86 if(i>0&&j>0) 87 Map[i+1][j+1]=(contx[i]-contx[i-1])*(conty[j]-conty[j-1]); 88 else if(i>0) 89 Map[i+1][j+1]=(contx[i]-contx[i-1])*conty[j]; 90 else if(j>0) 91 Map[i+1][j+1]=contx[i]*(conty[j]-conty[j-1]); 92 else 93 Map[i+1][j+1]=contx[i]*conty[j]; 94 } 95 } 96 int num=0; 97 for(int i=1; i<=contx.size(); i++) 98 { 99 for(int j=1; j<=conty.size(); j++) 100 { 101 if(vis[i][j])continue; 102 cnt=0; 103 dfs(i,j); 104 a[++num]=cnt; 105 } 106 } 107 sort(a+1,a+num+1); 108 printf("Case #%d:\n",++Case); 109 printf("%d\n",num); 110 for(int i=1; i<=num; i++) 111 { 112 if(i==1) 113 printf("%lld",a[i]); 114 else 115 printf(" %lld",a[i]); 116 } 117 printf("\n"); 118 } 119 return 0; 120 }
更多精彩
