[백준 2583] 영역 구하기

https://www.acmicpc.net/problem/2583

2583번: 영역 구하기

요구사항

흩어져 있는 영역의 숫자와 넓이 출력하기

 

풀이

입력이 거꾸로 주어지게 되는데 x, y만 바꿔서 생각해보면 똑같이 된다

이 후에는 dfs를 이용하여 영역을 찾아서 출력

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
vector<int> v;
int map[101][101];
int visit[101][101];
int n, m, k;
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
int cnt = 0;
void dfs(int r, int c) {
//	cout << "R" << r << "C" << c << endl;
	cnt++;
	for (int i = 0; i < 4; i++) {
		int nr = r + dr[i];
		int nc = c + dc[i];
		if (nr < 0 || nc < 0 || nr >= m || nc >= n)
			continue;
		if (map[nr][nc] == 0 && visit[nr][nc] == 0) {
			visit[nr][nc] = 1;
			dfs(nr, nc);
		}
	}
}
int main()
{
	cin >> n >> m >> k;
	for (int i = 0; i < k; i++)
	{
		int x1, x2, y1, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		int maxX = max(x1, x2);
		int minX = min(x1, x2);
		int minY = min(y1, y2);
		int maxY = max(y1, y2);
		//cout << maxX << " " << minX << " " << maxY << " " << minY << endl;
		for (int a = minX; a < maxX; a++) {
			for (int b = minY; b < maxY; b++)
			{
			//	cout << "A" << a << "B" << b << endl;
				map[a][b] = 1;
			}
		}
	}
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (map[i][j] == 0 && visit[i][j] == 0)
			{
				cnt = 0;
				visit[i][j] = 1;
				dfs(i, j);
				v.push_back(cnt);
			}
		}
	}
	cout << v.size() << endl;
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++) {
		printf("%d ", v.at(i));
	}
}