1619.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1619 on 2005-12-26 at 21:30:21 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int SIZE = 64;
const int MAX = SIZE*SIZE;

class UFSet {
public:
	int parent[MAX];
	void makeSet();
	int find(int);
	void unionSet(int, int);
};
void UFSet::makeSet() {
	memset(parent, -1, sizeof(parent));
}
int UFSet::find(int x) {
	if(parent[x] == -1) return x;
	else {
		parent[x] = find(parent[x]);
		return parent[x];
	}
}
void UFSet::unionSet(int x, int y) {
	int pX = find(x), pY = find(y);
	if(pX != pY) parent[pX] = pY;
}

int main()
{
	char map[SIZE][SIZE];
	UFSet block, dot;
	int w, h, i, j, t;
	int point[MAX], pn;
	int oa[MAX], pa[MAX];
	
	for(t = 1; scanf("%d %d", &w, &h) != EOF && w*h != 0; t++) {
		block.makeSet(); dot.makeSet(); getchar(); pn = 0;
		for(i = 0; i < h; i++) {
			gets(map[i]);
			for(j = 0; j < w; j++) {
				if(map[i][j] == 'X') {
					point[pn++] = i*w+j;
					if(i != 0 && map[i-1][j] == 'X') dot.unionSet((i-1)*w+j, i*w+j);
					if(j != 0 && map[i][j-1] == 'X') dot.unionSet(i*w+j, i*w+j-1);
				}
				if(map[i][j] != '.') {
					if(i != 0 && map[i-1][j] != '.') block.unionSet((i-1)*w+j, i*w+j);
					if(j != 0 && map[i][j-1] != '.') block.unionSet(i*w+j, i*w+j-1);
				}
			}
		}
		int f[MAX] = { 0 }, fn = 0;
		memset(oa, -1, sizeof(oa)); memset(pa, -1, sizeof(pa));
		for(i = 0; i < pn; i++) {
			int po = dot.find(point[i]);
			if(pa[po] != -1) continue;
			pa[po] = 0;
			int p = block.find(po);
			if(oa[p] == -1) oa[p] = fn++;
			f[oa[p]]++;
		}
		sort(f, f+fn);
		printf("Throw %d\n", t);
		for(i = 0; i < fn; i++) {
			printf("%d", f[i]);
			if(i == fn-1) putchar('\n');
			else putchar(' ');
		}
		putchar('\n');
	}
	
	return 0;
}