[정올 1457] 영역 구하기

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=729&sca=99&sfl=wr_hit&stx=1457 

JUNGOL

#include <stdio.h>
int R, C, K, grid[110][110], cnt, area[2550], area2[2550], s, e;
struct Point {
	int r, c;
} buf[50000];
Point delta[4] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };

void push_back(int r, int c) {
	buf[e].r = r;
	buf[e++].c = c;
}
Point& pop() {
	return buf[s++];
}

int BFS(int r, int c) {
	int areacnt = 0, newr, newc;
	s = 0, e = 0;
	push_back(r, c);
	while (s <= e) {
		const Point& rp = pop();
		if (grid[rp.r][rp.c]) continue;
		grid[rp.r][rp.c] = 1;
		areacnt++;
		for (int i = 0; i < 4; i++) {
			newr = rp.r + delta[i].r;
			newc = rp.c + delta[i].c;
			if (newr < 0 || newc < 0 || grid[newr][newc] != 0) continue; //경계 밖이거나 못 가는 곳이면
			push_back(newr, newc);
		}
	}
	return areacnt;
}

void mergesort(int s, int e) {
	if (s >= e) return;
	int m = (s + e) / 2;
	mergesort(s, m);
	mergesort(m + 1, e);
	
	int a = s, b = m + 1, k = s;

	while (a <= m && b <= e) {
		if (area[a] > area[b]) area2[k++] = area[b++];
		else area2[k++] = area[a++];
	}
	while (a <= m) area2[k++] = area[a++];
	while (b <= e) area2[k++] = area[b++];
	for (int i = s; i <= e; i++) area[i] = area2[i];
}

int main(void) {
	//freopen("input.txt", "r", stdin);
	scanf("%d%d%d", &R, &C, &K);
	int r1, r2, c1, c2;
	for (int i = 0; i < C; i++) grid[R][i] = 8;
	for (int i = 0; i < R; i++) grid[i][C] = 8;
	for (int i = 0; i < K; i++) {
		scanf("%d%d%d%d", &c1, &r1, &c2, &r2); //왼쪽아래, 오른쪽위
		for (int a = r1; a < r2; a++) {
			for (int b = c1; b < c2; b++) grid[a][b] = 2;
		}
	}
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (grid[i][j]) continue; //이미 있는 곳 패스
			area[cnt++] = BFS(i, j); //면적 구해서 넣기
		}
	}
	mergesort(0, cnt - 1);
	printf("%d\n", cnt);
	for (int i = 0; i < cnt; i++) printf("%d ", area[i]);

	return 0;
}