AOJ 0531 Paint Color

問題文→AIZU ONLINE JUDGE

テープが貼ってあるので、囲まれる領域の数を答える問題。

座標圧縮+幅優先でいける。

座標圧縮の解説が少なすぎて萎え...

一応この問題、第7回JOIの本選5番なのでそこの解説を見れば座標圧縮の大まかな説明が載っている→

書く量多すぎるので、テンプレ整備しよう...

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<cstdlib>
#include<climits>
#include<cstring>
#include<queue>
#include<deque>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define INF 99999999
#define EPS 0.0001
using namespace std;
typedef vector<string> VS;
typedef pair<int,int>PI;
int W,H,N;
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
int x1[1000],x2[1000],y1[1000],y2[1000];
int X,Y;
bool v[3000][3000];
vector<int>x,y;
int main(){
  while(cin>>W>>H,(W|H)){
    cin>>N;
    x.clear();y.clear();
    REP(i,N){
      cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
      x.push_back(x1[i]); y.push_back(y1[i]);
      x.push_back(x2[i]); y.push_back(y2[i]);
    }
    x.push_back(0),y.push_back(0);
    x.push_back(W),y.push_back(H);
    sort(x.begin(),x.end());
    sort(y.begin(),y.end());
    x.erase(unique(x.begin(),x.end()),x.end());
    y.erase(unique(y.begin(),y.end()),y.end());
    X=x.size(),Y=y.size();
    REP(i,N){
      x1[i]=lower_bound(x.begin(),x.end(),x1[i])-x.begin();
      y1[i]=lower_bound(y.begin(),y.end(),y1[i])-y.begin();
      x2[i]=lower_bound(x.begin(),x.end(),x2[i])-x.begin();
      y2[i]=lower_bound(y.begin(),y.end(),y2[i])-y.begin();
    }
    REP(i,Y) 
      REP(j,X)
      v[i][j]=i==Y-1||j==X-1;
    REP(i,N)
      for(int a=x1[i];a<x2[i];a++)
	for(int b=y1[i];b<y2[i];b++)
	  v[b][a]=1;
    int res=0;
    REP(i,Y){
      REP(j,X){
	if(v[i][j]) continue;
	res++;
	v[i][j]=1;
	queue<PI>Q; Q.push(make_pair(i,j));
	while(!Q.empty()){
	  int a=Q.front().first,b=Q.front().second;Q.pop();
	  REP(d,4){
	    int ny=a+dy[d],nx=b+dx[d];
	    if(ny<0 || nx<0 || ny>=Y-1 || nx>=X-1 || v[ny][nx]) continue;
	    v[ny][nx]=1;
	    Q.push(make_pair(ny,nx));
	  }
	}
      }
    }
    cout<<res<<endl;
  }
}