首页 > 代码库 > AOJ 0531：Paint Color（二维离散+imos）
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;}
AOJ 0531：Paint Color（二维离散+imos）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。