#BOJ 2583領域を取得

🖼 面積を求める
( https://www.acmicpc.net/problem/2583 )

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	25275	14108	11201	56.420%

質問する
ルーラーピッチ1のM×N(M,N≦100)サイズの四角紙があります.この四角紙にK個の矩形を目盛りで描画すると、これらK個の矩形の内部を除いて、残りの部分はいくつかの別々の領域に分割される.
例えば、M=5、N=7の四角紙に<図1>のように3つの矩形を描くと、残りの領域は<図2>のように3つの独立した領域に分割される.
「図2」に示すように、3つの領域の幅はそれぞれ1、7、13である.
M,N,K,K個の矩形の座標が与えられると,K個の矩形の内部を除いた残りの部分をいくつかの独立した領域に分割し,各分離領域の幅を求めることで出力プログラムを記述する.
入力
第1行MとN,Kは、スペースを隔てて順次与えられる.M,N,Kはいずれも100以下の自然数である.2行目からK行目まで、矩形左下角頂点のx、y座標値、右上角頂点のx、y座標値は、行ごとにスペースを隔てて順次与えられる.四角い紙の左下の頂点の座標は(0,0)、右上の頂点の座標は(N,M)です.入力したK個の長方形は、丸み紙全体を埋めません.
しゅつりょく
最初の行の区切り領域の数を出力します.2行目は各領域の幅を昇順に並べ、スペースを隔てて印刷します.
入力例1
5 7 3
0 2 4 4
1 1 2 5
4 0 6 2
サンプル出力1
3
1 7 13
インプリメンテーション

#include <bits/stdc++.h>
using namespace std;

int graph[102][102];
bool vis[102][102];

int m, n; //m : 가로 , n : 세로

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

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);

	int k; // 직사각형의 개수
	cin >> m >> n >> k; //가로 세로 직사각형 개수 입력

	for( int w = 0 ; w < k ; w ++)
	{
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		for (int i = x1; i < x2; i++)
		{
			for (int j = y1; j < y2; j++)
			{
				graph[i][j] = 1;
			}
		}
	}

	//이제 0인 구역을 bfs 돌려서 찾으면 됨
	vector<int> area; // 영역의 넓이를 저장할 가변길이배열 선언
	queue<pair<int, int>> Q;
	int count = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (graph[i][j] == 1 || vis[i][j] == true) continue;
			//0이고 아직 방문안했다면 아래
			count++;
			vis[i][j] = true;
			Q.push({ i,j }); // 좌표 입력

			int is_area = 0;

			while (!Q.empty())
			{
				auto cur = Q.front(); Q.pop();
				is_area++;
				for (int dir = 0; dir < 4; dir++)
				{
					int nx = cur.first + dx[dir];
					int ny = cur.second + dy[dir];

					if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
					if (graph[nx][ny] == 1 || vis[nx][ny] == true) continue;
					Q.push({ nx,ny });
					vis[nx][ny] = true;
				}
				
			}
			area.push_back(is_area);
		}
	}
	sort(area.begin(), area.end());
	cout << count << '\n';
	for (auto& a : area)
	{
		cout << a << ' ';
	}
	

	return 0;
}