[백준] 2583번 영역 구하기 (BFS)

-문제

 

-코드

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

int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int main()
{
	int n, m, k, cnt=0;
	int ax, ay, bx, by;
	scanf("%d %d %d", &n, &m, &k);

	vector<vector<int> > a(n, vector<int>(m,0));
	queue<pair<int, int> > q;
	vector<int> res;

	for (int i = 0; i < k; i++)
	{
		scanf("%d %d %d %d", &ay, &ax, &by, &bx);

		for (int x = n-bx;  x < n-ax; x++ )
		{
			for (int y = ay; y < by; y++)
			{
				a[x][y] = 1;
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (a[i][j] == 0)
			{
				q.push({ i,j });
				a[i][j] = 1;
				cnt = 1;
				while (!q.empty())
				{
					pair<int, int> tmp = q.front();
					q.pop();
					for (int h = 0; h < 4; h++)
					{
						int xx = tmp.first + dx[h];
						int yy = tmp.second + dy[h];
						if (xx < 0 || yy < 0 || xx >= n || yy >= m) continue;
						if (a[xx][yy] == 0)
						{
							a[xx][yy] = 1;
							q.push({ xx,yy });
							cnt++;
						}
					}
				}
				if (cnt>0) res.push_back(cnt);
				
			}

		}
	}

	sort(res.begin(), res.end());
	printf("%d\n", res.size());

	for (int i = 0; i < res.size(); i++)
	{
		printf("%d ", res[i]);
	}


	return 0;
}