Codeforces Beta Round #31 D : Chocolate

問題概要

W*H(W,H<100)のサイズのチョコレートがある。座標(x1,y1)~(x2,y2)に沿ってチョコレート割したという情報がバラバラの順序で与えられる。割った後のカケラのサイズを全て出力する問題。

解法

座標を2倍にすると単純なFlood Fillに落ちる。切る順番は考えなくてよい。

practiceで通ったコード

計算量O(W*H)。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_W = 100;
const int MAX_N = 100;
const int dy[] = {0, 0, 1, -1}, dx[] = {1, -1, 0, 0};

int H, W, N;
bool visited[2*MAX_W+1][2*MAX_W+1];
int ans[MAX_N + 1];

int dfs(int y, int x){
	visited[y][x] = true;
	int ret = y&x&1;

	for(int k=0; k<4; k++){
		int ny = y + dy[k], nx = x + dx[k];
		if(0<=ny && ny<=2*H && 0<=nx && nx<=2*W && !visited[ny][nx]){
			ret += dfs(ny, nx);
		}
	}

	return ret;
}

int main(){
	scanf("%d%d%d",&W,&H,&N);

	for(int i=0; i<N; i++){
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

		if(x1 == x2){
			for(int j=2*y1; j<=2*y2; j++){
				visited[j][2*x1] = true;
			}
		}
		else{
			for(int j=2*x1; j<=2*x2; j++){
				visited[2*y1][j] = true;
			}
		}
	}

	int p = 0;
	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			if(!visited[2*i+1][2*j+1]){
				ans[p++] = dfs(2*i+1, 2*j+1);
			}
		}
	}

	sort(ans, ans+N+1);
	for(int i=0; i<N+1; i++){
		printf("%d%c", ans[i], i==N?'\n':' ');
	}

	return 0;
}