언제품?

: 220908

주의사항

: 모든 노드에 대해서 탐색을 하는 것이 아니라, 조건에 맞는
원소들만 탐색하도록 해야 함..

• 메인 부에서 탐색 시작할 때도 주의하자...

풀이 전략

• 너비를 구하는 거여서 dfs 4개 들어가는 방향 바뀔 때마다 카운팅 할 까?
  생각했는데 ,, 아닌 것 같아서 다시 생각해봄.

• 입력으로 들어오는 좌표 번호로 접근하지 말고,
  사각형 중앙을 하나의 좌표로 보고 접근해서 생각하면
  쉽게 접근할 수 있음.

맨 밑의 0,0 부분의 쪽의 첫번째 사각형의 중간 pos 을 0, 0 으로 놓자.

예를 들어서 첫번째 0 2 4 4 에 대해 분석을 하자.
문제가 되는 부분은 시작점 : 0,2 ~ 오른쪽 상단 끝점이 4,4 인데
-> 4,4 를 -1 -1 씩 빼서 3,3 으로 만들자.
-> 그러면 0(x),2(y) ~ 3(x) , 3(y) 이렇게 만들 수 있음.

두번째 줄 1 1 2 5
시작 사각형 pos : 1 1 ~
오른쪽 상단 사각형 pos : 1 4

세번째 줄 4 0 6 2
시작 사각형 pos : 4 0
오른쪽 사각형 pos : 5 1

그림으로 그려보면

-> 아 됬으!

코드

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

int m, n, k;
// 첫번째가  y임
// 두번째가  x임

bool dfs(vector<vector<int>>&v, int _x, int _y , int &cnt)
{
	if (_x < 0 || _x >= n || _y < 0 || _y >= m)
		return false;
	
	if (v[_y][_x] == 1)
		return false;
	v[_y][_x] = 1;
	cnt++;
	dfs(v, _x + 1, _y, cnt);
	dfs(v, _x - 1, _y, cnt);
	dfs(v, _x , _y + 1, cnt);
	dfs(v, _x , _y - 1, cnt);


	return true;
}


int main()
{	
	cin >> m >> n >> k;
	vector<vector<int>>v(m, vector<int>(n, 0));
	

	for (int i = 0; i < k; i++)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;

		//  복잡해서 뒤집었음.
		for (int y = a; y < c; ++y)
		{
			for (int x = b; x < d; ++x)
			{
				v[x][y] = 1;
			}
		}
	}

	// 함수 진입 할 때의 카운팅이 빈칸의 개수를 의미함.
	int rectCnt = 0;
	vector<int>rect;
	// 빈칸의 넓이를 구하는 것은 dfs 내부에서 처리함.
	for (int i = 0; i < m; i++)
	{
		int cnt = 0;

		for (int j = 0; j < n; ++j)
		{
			if (v[i][j] == 1)
				continue;

			if (dfs(v, j, i, cnt))
			{
				rectCnt++;
				rect.push_back(cnt);
				cnt = 0;
			}
		}
	}

	cout << rectCnt << endl;
	
	sort(begin(rect), end(rect));
	for (auto iter : rect)
		cout << iter << " ";

}