UVALive 6663 Count the Regions (离散化，染色，dfs)
来源：程序员人生 发布时间：2014-10-07 08:00:01 阅读次数：2569次
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4675
题意：
二维平面内给出若干矩形，平面被矩形的边分为若干个区域，求一共有多少区域。
分析：
由于矩形只有50个，离散化后的平面大约是100*100的。不妨对于每个矩形覆盖的区域进行染色（用二进制位状压），相同颜色的联通块就是一个区域，只要dfs找联通块的个数即可。值得注意的是还需要对原平面进行染色，而不能直接在最后的数量上加1（最外面无穷大的区域），这样中间镂空的区域就无法计算了。
还有一个问题是区间的开闭。比赛时读入数据后对x2--;y2--;染色时i<=x2;j<=y2;得到WA;后来去掉x2--;y2--;染色时改为i<x2;j<y2;后就能AC。可能是因为离散化了，但我仍未找出反例，知道原因的朋友请告诉我。
#include <bits/stdc++.h>
#define maxn 233
#define INF 0x3f3f3f3f
using namespace std;
struct _rectangle
{
int x1,y1,x2,y2;
}rec[64];
long long G[maxn][maxn];
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
int x[maxn],y[maxn];
int XN,YN;
inline bool
in_range(int x,int y)
{
return 0<=x && x<XN && 0<=y && y<YN;
}
void
dfs(int x,int y,long long status)
{
G[x][y]=0;
for (int i=0;i<4;i++)
{
int tx=x+dx[i],ty=y+dy[i];
if (in_range(tx,ty) && G[tx][ty]==status) dfs(tx,ty,status);
}
}
int
main()
{
#ifdef FCBRUCE
freopen("/home/fcbruce/code/t","r",stdin);
#endif // FCBRUCE
int n;
while (scanf("%d",&n),n)
{
int cnt=0;
int minx=INF,miny=INF,maxx=-1,maxy=-1;
for (int i=0,x1,y1,x2,y2;i<n;i++)
{
scanf("%d%d%d%d",&x1,&y2,&x2,&y1);
minx=min(minx,min(x1,x2));
maxx=max(maxx,max(x1,x2));
miny=min(miny,min(y1,y2));
maxy=max(maxy,max(y1,y2));
rec[i]=(_rectangle){x1,y1,x2,y2};
x[cnt]=x1;y[cnt]=y1;
cnt++;
x[cnt]=x2;y[cnt]=y2;
cnt++;
}
minx--;miny--;
maxx++;maxy++;
rec[n++]=(_rectangle){minx,miny,maxx,maxy};
x[cnt]=minx;y[cnt]=miny;
cnt++;
x[cnt]=maxx;y[cnt]=maxy;
cnt++;
sort(x,x+cnt);sort(y,y+cnt);
XN=unique(x,x+cnt)-x;
YN=unique(y,y+cnt)-y;
memset(G,0,sizeof G);
for (int k=0,x1,y1,x2,y2;k<n;k++)
{
x1=lower_bound(x,x+XN,rec[k].x1)-x;
y1=lower_bound(y,y+YN,rec[k].y1)-y;
x2=lower_bound(x,x+XN,rec[k].x2)-x;
y2=lower_bound(y,y+YN,rec[k].y2)-y;
for (int i=x1;i<x2;i++)
{
for (int j=y1;j<y2;j++)
{
G[i][j]|=(1ll<<k);
}
}
}
int _cnt=0;
for (int i=0;i<XN;i++)
{
for (int j=0;j<YN;j++)
{
if (G[i][j]!=0ll)
{
dfs(i,j,G[i][j]);
_cnt++;
}
}
}
printf("%d
",_cnt);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
