2583 : 영역 구하기

풀이

직사각형 영역에 체크를 해놓고

모든 칸을 돌면서 bfs나 dfs나 아무거나 돌려주면 된다.

입력이 좀 짜증난다 (…)

코드

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

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

int n, m, k, cnt, a[111][111];
vector<int> v;

int dfs(int x, int y) {
	int ret = 1;
	a[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
		if (!a[nx][ny]) ret += dfs(nx, ny);
	}
	return ret;
}

int main() {
	scanf("%d %d %d", &n, &m, &k);
	while (k--) {
		int e, b, c, d;
		scanf("%d %d %d %d", &e, &b, &c, &d);
		for (int i = b; i < d; i++)
			for (int j = e; j < c; j++)
				a[i][j] = 1;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!a[i][j]) v.push_back(dfs(i, j));
		}
	}

	sort(v.begin(), v.end());
	printf("%d\n", v.size());
	for (auto now : v) printf("%d ", now);

	return 0;
}#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

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

int n, m, k, cnt, chk[111][111];
vector<int> v;

int dfs(int x, int y) {
	int ret = 1;
	chk[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
		if (!chk[nx][ny]) ret += dfs(nx, ny);
	}
	return ret;
}

int main() {
	scanf("%d %d %d", &n, &m, &k);
	while (k--) {
		int a, b, c, d;
		scanf("%d %d %d %d", &a, &b, &c, &d);
		for (int i = b; i < d; i++)
			for (int j = a; j < c; j++)
				chk[i][j] = 1;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!chk[i][j]) v.push_back(dfs(i, j));
		}
	}

	sort(v.begin(), v.end());
	printf("%d\n", v.size());
	for (int i : v) printf("%d ", i);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-05-22 17:23

Read more posts by this author