AOJ 0531:Paint Color(二维离散+imos)

【题目链接】 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0531

【题目大意】

  给出一张图,和一些矩形障碍物,求该图没被障碍物覆盖的部分被划分为几个连通块

【题解】

  首先对图中的点进行离散化,对于一个障碍物来说,
  我们将其看做左闭右开上闭下开的图形,所以在离散的时候只要离散障碍物的点即可。
  之后我们利用imos积累法得出哪些部分是障碍物,就可以统计连通块了。

【代码】

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <queue>
using namespace std;
const int N=1050,dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int n,H,W,X1[N],X2[N],Y1[N],Y2[N];
int imos[2*N][2*N];
int compress(int *x1,int *x2,int w){
vector<int>xs;
for(int i=0;i<n;i++){
int tx1=x1[i],tx2=x2[i];
if(1<=tx1&&tx1<w)xs.push_back(tx1);
if(1<=tx2&&tx2<w)xs.push_back(tx2);
}xs.push_back(0);xs.push_back(w);
sort(xs.begin(),xs.end());
xs.erase(unique(xs.begin(),xs.end()),xs.end());
for(int i=0;i<n;i++){
x1[i]=find(xs.begin(),xs.end(),x1[i])-xs.begin();
x2[i]=find(xs.begin(),xs.end(),x2[i])-xs.begin();
}return xs.size()-1;
}
int bfs(){
int ans=0;
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(imos[i][j])continue;
ans++;
queue<pair<int,int> >que;
que.push(make_pair(j,i));
while(!que.empty()){
int nx=que.front().first,ny=que.front().second;
que.pop();
for(int i=0;i<4;i++){
int tx=nx+dx[i],ty=ny+dy[i];
if(tx<0||W<tx||ty<0||H<ty||imos[ty][tx]>0)continue;
que.push(make_pair(tx,ty));
imos[ty][tx]=1;
}
}
}
}return ans;
}
int main(){
while(~scanf("%d%d",&W,&H),W||H){
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d%d%d%d",&X1[i],&Y1[i],&X2[i],&Y2[i]);
memset(imos,0,sizeof(imos));
W=compress(X1,X2,W);H=compress(Y1,Y2,H);
for(int i=0;i<n;i++){
imos[Y1[i]][X1[i]]++;
imos[Y1[i]][X2[i]]--;
imos[Y2[i]][X1[i]]--;
imos[Y2[i]][X2[i]]++;
}for(int i=0;i<H;i++)for(int j=1;j<W;j++)imos[i][j]+=imos[i][j-1];
for(int j=0;j<W;j++)for(int i=1;i<H;i++)imos[i][j]+=imos[i-1][j];
printf("%d\n",bfs());
}return 0;
}

  

上一篇:.NET Core项目NLog日志框架使用


下一篇:Web项目中使用NLog记录日志,利用单件模式控制整个项目只有一个Logger对象的问题...