#include <stdio.h>
int paper[100][100]={0};
int squ[100][4]={0};
int size[100]={0};
int m, n, cnt;
void paint(int a); //사각형이 차지하는 부분 채우기
int count(void); //빈공간 위치 찾기
int re(int a, int b); //빈공간 크기 계산
void line(int c); //오름차순으로 정렬
int main(void)
{
int k, i, c;
//입력 시작
scanf(" %d %d %d", &m, &n, &k);
for(i=0; i<k; i++)
{
scanf("%d %d %d %d", &squ[i][0], &squ[i][1], &squ[i][2], &squ[i][3]);
paint(i); //사각형이 차지하는 부분 1로 채우기
}
//입력 끝
c=count();
line(c);
//출력 시작
printf("%d\n", c);
for(i=0; i<c; i++)
printf("%d ", size[i]);
//출력 끝
return 0;
}
void paint(int a)
{
int i, j;
for(i=squ[a][1]; i<squ[a][3]; i++)
{
for(j=squ[a][0]; j<squ[a][2]; j++)
paper[i][j]=1; //사각형인 부분은 1로 채우기
}
}
int count(void)
{
int i, j, a, c=0;
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
{
if(paper[i][j]==0) //빈공간의 위치
{
cnt=0;
re(i, j);
size[c++]=cnt;
//printf("%d \n", cnt);
}
}
}
return c;
}
int re(int a, int b)
{
if(a>=0 && b>=0 && a<m && b<n)
{
if(paper[a][b]==0)
{
paper[a][b]=2; //이미 센 부분은 채워두기
cnt++;
re(a, b+1);
re(a, b-1);
re(a+1, b);
re(a-1, b);
}
}
else
return 0;
}
void line(int c) //오름차순 정렬
{
int i, j, min, temp;
for(i=0; i<(c-1); i++)
{
min=i;
for(j=i+1; j<c; j++)
{
if(size[min]>size[j])
min=j;
}
if(min!=i)
{
temp=size[min];
size[min]=size[i];
size[i]=temp;
}
}
}
2018.03.31 11:52
정올 - 알고리즘 - 영역구하기(1457)
조회 수 475 추천 수 0 댓글 0