[C++] 백준 2583번: 영역 구하기

www.acmicpc.net/problem/2583

2583번: 영역 구하기

처음엔 모눈종이가 거꾸로 되있고 좌표로 직사각형을 입력받아야해서 조금 생각을 해야했다.

 

하지만 그 후엔 그냥 단순히 DFS를 구현하면 되는 쉬운 문제였다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int m, n, k, cnt;
int map[101][101];
int visit[101][101];
vector<int> ans;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1,0,-1,0 };

void dfs(int a, int b) {
	cnt++;
	for (int i = 0; i < 4; i++) {
		if (a + dx[i] >= 0 && a + dx[i] < n 
			&& b + dy[i] >= 0 && b +dy[i] < m
			&& visit[a + dx[i]][b + dy[i]] == 0 && map[a + dx[i]][b + dy[i]] == 0) {
			visit[a + dx[i]][b + dy[i]] = 1;
			dfs(a + dx[i], b + dy[i]);
		}
	}
	return;
}

int main() {
	int a, b, c, d;
	cin >> m >> n >> k;
	for (int i = 0; i < k; i++) {
		cin >> a >> b >> c >> d;
		for (int j = a; j < c; j++) {
			for (int k = b; k < d; k++) {
				map[j][k] = 1;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visit[i][j] == 0 && map[i][j] == 0) {
				visit[i][j] = 1;
				cnt = 0;
				dfs(i, j);
				ans.push_back(cnt);
			}
		}
	}
	sort(ans.begin(), ans.end());
	cout << ans.size() << "\n";
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << " ";
	}
	return 0;
}