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;

}