https://www.acmicpc.net/problem/2583
#include <iostream>
#include <algorithm>
#include <queue>
/*
*
*[문제]
*모눈종이 위에 논금에 맞추어서 K개의 직사각형ㅇ르 그린다.
*K의 내부를 제외한 부분이 몇 개로 나눠지는 가
*
*[입력]
*M,N K<=100
*M = 가로
*N = 세로
*K 개의 직사각형
*
*왼 아래 꼭짓점의 xy, 오른쪽 위 꼭지점의 xy
*모눈의 왼쪽 아래가 0,0이다.
*오른쪽 위는 N,M이다.
*
*k개의 직사각형들이 모눈 종이 전체를 채우는 경우 없다.
*
*/
using namespace std;
#define X first
#define Y second
int dx[4]={1,0,-1,0};
int dy[4]= {0,1,0,-1};
int m,n,k;
int board[102][102];
int vis[102][102];
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
cin >> m >> n>> k;
while(k--) {
int x1, y1,x2,y2;
cin >> x1>>y1 >> x2>> y2;
for(int j=y1; j<y2; j++) {
for(int k= x1; k<x2; k++) {
board[j][k] =1;
}
}
}
int count =0;
vector<int> ans;
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
if(board[i][j] == 1 || vis[i][j] ==1)continue;
queue<pair<int,int>>Q;
vis[i][j] =1;
Q.push({i,j});
int width = 1;
count++;
while(!Q.empty()) {
auto cur = Q.front();
Q.pop();
for(int dir=0; dir<4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if(nx<0 || ny <0 || nx >=m || ny >=n)continue;
if(board[nx][ny] ==1 || vis[nx][ny] ==1)continue;
Q.push({nx,ny});
vis[nx][ny] =1;
width++;
}
}
ans.push_back(width);
}
}
// for(int i=0; i<m; i++) {
// for(int k=0; k<n; k++) {
// cout << vis[i][k] << " ";
// }
// cout << " \n";
// }
sort(ans.begin(), ans.end());
cout << count << "\n";
for(int i: ans) cout << i << " ";
return 0;
}