首页 > 代码库 > UVALIve6663--Count the Regions【离散化+搜索】
UVALIve6663--Count the Regions【离散化+搜索】
题意:一个平面上给你最多50个矩形,可以相交、覆盖,问他们把平面分割成了几部分,整个图形外面广大的空白区域也算一部分。
记得以前见过这种题,当时不会做也没做。现在看到这题还是没想法。在吴琦的讲解和代码下终于弄明白了。
思路是这样,根据他给的坐标点,排序、去重,然后重新构建一个图,至少在相邻两个点之间空出一个点表示被分割的区域,这样之后才能进行搜索,这实际上是把整个图形压缩下来,将中间的空白区域缩小,然后再根据原来的边的信息在新的图里标记出边的信息。然后进行搜索
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 100005 #define eps 1e-7 #define INF 0x7FFFFFFF #define ff sqrt(5.0) typedef long long ll; struct node{ int l,t,r,b; }rec[60]; int x[120],y[120]; int mapp[210][210]; int xx[1000010],yy[1000010]; int lx,ly; int dir[4][2] = {1,0,-1,0,0,1,0,-1}; bool cango(int x,int y){ if(x>=1&&y>=1&&x<=2*lx-2&&y<=2*ly-2) return true; return false; } void dfs(int x,int y){ mapp[x][y] = 1; for(int i=0;i<4;i++){ int xx = x + dir[i][0]; int yy = y + dir[i][1]; if(cango(xx,yy)&&mapp[xx][yy]==0) dfs(xx,yy); } } int main(){ int n,i,ans,totx,toty; while(scanf("%d",&n),n){ ans = totx = toty = 0; memset(mapp,0,sizeof(mapp)); for(i=0;i<n;i++){ scanf("%d%d%d%d",&rec[i].l,&rec[i].t,&rec[i].r,&rec[i].b); x[totx++] = rec[i].l; y[toty++] = rec[i].t; x[totx++] = rec[i].r; y[toty++] = rec[i].b; } sort(x,x+totx); sort(y,y+toty); lx = unique(x,x+totx) - x; ly = unique(y,y+toty) - y; for(i=0;i<lx;i++){ xx[x[i]] = 2*i; } for(i=0;i<ly;i++){ yy[y[i]] = 2*i; } for(i=0;i<n;i++){ int t1 = xx[rec[i].l]; int t2 = yy[rec[i].t]; int t3 = xx[rec[i].r]; int t4 = yy[rec[i].b]; for(int j=t1;j<=t3;j++) mapp[j][t2] = mapp[j][t4] = 1; for(int j=t2;j>=t4;j--) mapp[t1][j] = mapp[t3][j] = 1; } for(i=0;i<2*lx;i++){ if(mapp[i][0]==0) dfs(i,0); if(mapp[i][2*ly-1]==0) dfs(i,2*ly-1); } for(i=0;i<2*ly;i++){ if(mapp[0][i]==0) dfs(0,i); if(mapp[2*lx-1][i]==0) dfs(2*lx-1,i); } for(i=0;i<2*lx;i++){ for(int j=0;j<2*ly;j++){ if(mapp[i][j]==0){ ans++; dfs(i,j); } } } cout<<ans+1<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。