POJ 3338 Rectangle Cutting

問題

hxwの長方形のケーキに対して、n個の長方形の切れ目を入れる。
それぞれの切れ目はx1,y1,x2,y2によって指定される。

全ての切れ目を入れ終えた後、ケーキはいくつの部分に分割されているか求めよ。

制約条件

h,w≦20
n≦50
座標およびh,wは全て整数

方針

線分を全てboolの配列に入れて、塗りつぶしのdfsする。

ソースコード

const int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
int h,w,n;
bool tate[21][21],yoko[21][21];
bool v[21][21];
void dfs(int y,int x){
	v[y][x]=1;
	rep(d,4){
		int ny=y+dy[d],nx=x+dx[d];
		if(ny<0||nx<0||ny>=h||nx>=w||v[ny][nx])continue;
		if(d==0&&yoko[y][x]||d==1&&tate[y][x]||d==2&&yoko[y+1][x]||d==3&&tate[y][x+1])continue;
		dfs(ny,nx);
	}
}
int main(){
	while(scanf("%d%d",&h,&w),h){
		scanf("%d",&n);
		memset(tate,0,sizeof(tate));
		memset(yoko,0,sizeof(yoko));
		memset(v,0,sizeof(v));
		
		rep(i,n){
			int x1,y1,x2,y2;
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			if(x1>x2)swap(x1,x2);
			if(y1>y2)swap(y1,y2);
			
			for(int x=x1;x<x2;x++)yoko[y1][x]=yoko[y2][x]=1;
			for(int y=y1;y<y2;y++)tate[y][x1]=tate[y][x2]=1;
		}
		int ans=0;
		rep(i,h)rep(j,w)if(!v[i][j])dfs(i,j),ans++;
		printf("%d\n",ans);
	}
	return 0;
}