第７回日本情報オリンピック 本選 「ペンキの色」

難しい。

解法についてはJOIの解法を見るよりこちらを参照したほうがいい気がします。

AOJ 0531 : Paint Color - きままにものづくり

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
#include <iostream>
using namespace std;

typedef pair<int,int> P;

int w,h,n;

int dx[4] = {0,-1,1,0};
int dy[4] = {1,0,-0,-1};

int x1[1003],x2[1003],y1[1003],y2[1003];

bool fid[6003][6003];

int compress(int *X1,int *X2,int W){
  vector<int> xs;
  
  for(int i = 0;i < n;i++){
    for(int d = -1;d <= 1;d++){
      int tx1 = X1[i] + d,tx2 = X2[i] + d;
      if(0 <= tx1 && tx1 <= W) xs.push_back(tx1);
      if(0 <= tx2 && tx2 <= W) xs.push_back(tx2);
    }
  }
  
  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 (int)xs.size()-1;
}

int main(){
  
  while(1){

  scanf("%d%d",&w,&h);
  
  if(w == 0)break;
  scanf("%d",&n);
  w *= 2;
  h *= 2;
  for(int i = 0;i < n;i++){
    scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]);
    x1[i]*=2;x2[i]*=2;y1[i]*=2;y2[i]*=2; 
  }
  
  w = compress(x1,x2,w);
  h = compress(y1,y2,h);
  
  memset(fid,0,sizeof(fid));
  
  for(int i = 0;i < n;i++){
    for(int y = y1[i];y <= y2[i];y++){
      for(int x = x1[i];x <= x2[i];x++){
	fid[y][x] = true;
      }
    }
  }
  
  int ans = 0;
  
  for(int y = 0;y <= h;y++){
    for(int x = 0;x <= w;x++){
      if(fid[y][x])continue;
      ans++;
      
      queue<P> que;
      que.push(P(x,y));
      while(que.size()){
	int nx = que.front().first,ny = que.front().second;
	que.pop();
	
	for(int i = 0;i < 4;i++){
	  int nnx = nx + dx[i];
	  int nny = ny + dy[i];
	  if(nny < 0 || nnx < 0 || nnx > w || nny > h)continue;
	  if(fid[nny][nnx])continue;
	  que.push(P(nnx,nny));
	  fid[nny][nnx] = true;
	}
      }
    }
  }
  

  
  printf("%d\n",ans);
  }
  return 0;
}