首页 > 代码库 > [ An Ac a Day ^_^ ] hdu 5925 Coconuts 离散化+BFS求连通块

[ An Ac a Day ^_^ ] hdu 5925 Coconuts 离散化+BFS求连通块

东北赛根本就没看懂的的题目……

也用到了离散化

1e9的x y范围 200个坏点 很典型的离散化数据范围

还是不太为什么离散化的遍历下标都要从1开始……

所以说只做这道题对离散化的理解还不是很深刻……

因为可能换一道题又不会了

还是要多做啊

 

  1 #include<bits/stdc++.h>  2 #define cl(a,b) memset(a,b,sizeof(a))  3 #define debug(x) cerr<<#x<<"=="<<(x)<<endl  4 using namespace std;  5 typedef long long ll;  6   7 const int maxn=2e2+10;  8   9 int dx[4]= {0,0,1,-1}; 10 int dy[4]= {1,-1,0,0}; 11  12 ll ans[maxn*maxn],sum; 13 int n,m,k,cntx,cnty; 14 int x[maxn],y[maxn]; 15 int xx[maxn],yy[maxn]; 16 int linex[maxn],liney[maxn]; 17 bool vis[maxn][maxn]; 18 map<int,int>ux,uy;//如果用数组的话会因为x y太大越界 所以这里用map映射 19  20 void init() 21 { 22     cntx=0,cnty=0; 23     cl(ans,0),cl(vis,0); 24     ux.clear(),uy.clear(); 25 } 26  27 bool judge(int x,int y) 28 { 29     if(x<1||x>cntx||y<1||y>cnty||vis[x][y]) return false; 30     return true; 31 } 32  33 void dfs(int x,int y) 34 { 35     if(!judge(x,y)) return ; 36     vis[x][y]=true; 37     sum+=1ll*linex[x]*liney[y]; 38     for(int i=0;i<4;i++) 39         dfs(x+dx[i],y+dy[i]); 40 } 41  42 int main() 43 { 44     int cas=1,T; 45     scanf("%d",&T); 46     while(T--) 47     { 48         init(); 49         scanf("%d%d%d",&n,&m,&k); 50         int nx=0,ny=0; 51         xx[++nx]=1,xx[++nx]=n; 52         yy[++ny]=1,yy[++ny]=m; 53         for(int i=1;i<=k;i++) 54         { 55             scanf("%d%d",&x[i],&y[i]); 56             xx[++nx]=x[i],yy[++ny]=y[i]; 57         } 58         //离散化x轴 59         sort(xx+1,xx+nx+1); 60         nx=unique(xx+1,xx+nx+1)-(xx+1); 61         for(int i=1;i<=nx;i++) 62         { 63             if(xx[i]!=xx[i-1]+1) 64             { 65                 linex[++cntx]=xx[i]-(xx[i-1]+1); 66             } 67             linex[++cntx]=1; 68             ux[xx[i]]=cntx; 69         } 70         //离散化y轴 71         sort(yy+1,yy+ny+1); 72         ny=unique(yy+1,yy+ny+1)-(yy+1); 73         for(int i=1;i<=ny;i++) 74         { 75             if(yy[i]!=yy[i-1]+1) 76             { 77                 liney[++cnty]=yy[i]-(yy[i-1]+1); 78             } 79             liney[++cnty]=1; 80             uy[yy[i]]=cnty; 81         } 82         //标记bad coconut 83         for(int i=1;i<=k;i++) 84         { 85             vis[ux[x[i]]][uy[y[i]]]=true; 86         } 87         //搜索联通块并记录ans 88         int cnt=0; 89         for(int i=1;i<=cntx;i++) 90         { 91             for(int j=1;j<=cnty;j++) 92             { 93                 if(!vis[i][j]) 94                 { 95                     sum=0; 96                     dfs(i,j); 97                     ans[cnt++]=sum; 98                 } 99             }100         }101         sort(ans,ans+cnt);102         printf("Case #%d:\n",cas++);103         printf("%d\n",cnt);104         for(int i=0;i<cnt;i++)105             printf("%lld%c",ans[i],i==cnt-1?\n: );106     }107     return 0;108 }109 /*110 111 2112 113 3 3114 2115 1 2116 2 1117 118 3 3119 1120 2 2121 122 */

 

[ An Ac a Day ^_^ ] hdu 5925 Coconuts 离散化+BFS求连通块