UVALive 6663 Count the Regions (離散化，染色，dfs)
來源：程序員人生 發布時間：2014-10-07 08:00:01 閱讀次數：2705次
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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
