정올 영역구하기

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=729&sca=30&sfl=wr_subject

#include<stdio.h>

/*

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다.

이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이

몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면,

그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

efc6e5f9d670c6da62174cf11a66a8c2_1449731

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이

몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

[Copy] 5 7 3 0 2 4 4 1 1 2 5 4 0 6 2

[Copy] 3 1 7 13

*/

typedef struct {

int sX;

int sY;

int eX;

int eY;

} _pos;

_pos POS[1000];

int map[100][100] = { 0, };

int nCount = 0;

int nArea = 0;

int Area[100] = { 0, };

int sero;

int garo;

int idx = -1;

void find(int se, int ga)

{

nCount++;

if (se - 1 >= 0 && map[se - 1][ga] == 0) 

{

map[se - 1][ga] = idx;

find(se - 1, ga); 

}

if (se + 1 < sero && map[se + 1][ga] == 0)

{ 

map[se + 1][ga] = idx; 

find(se + 1, ga); 

}

if (ga - 1 >= 0 && map[se][ga - 1] == 0) 

{ 

map[se][ga - 1] = idx; 

find(se, ga - 1); 

}

if (ga + 1 < garo && map[se][ga + 1] == 0)

{ 

map[se][ga + 1] = idx;

find(se, ga + 1); 

}

//int Dy[] = { 1, 0,0, -1 };

//int Dx[] = { 0,-1, 1, 0 };

//nArea++;

//int head = 0;

//int tail = 1;

//while (1)

//{

// for (int x = 0; x < 4; x++)

// {

// int tmpX = garo + Dx[x];

// int tmpY = sero + Dy[x];

// if (map[tmpY][tmpX] == 0)

// {

// map[tmpY][tmpX] == -1;

// nCount++;

// }

// }

//}

}

void main()

{

int count;

// freopen("input.txt", "r", stdin);

scanf("%d %d %d", &sero, &garo, &count);

for (int i = 0; i < count; i++)

{

scanf("%d %d %d %d", &POS[i].sX, &POS[i].sY, &POS[i].eX, &POS[i].eY);

int tmpX = POS[i].eX - POS[i].sX;

int tmpY = POS[i].eY - POS[i].sY;

for (int y = POS[i].sY; y < tmpY + POS[i].sY; y++)

{

for (int x = POS[i].sX; x < tmpX + POS[i].sX; x++)

{

map[y][x]++;

}

}

}

for (int i = 0; i< sero; i++)

{

for (int j = 0; j < garo; j++)

{

if (map[i][j] == 0)

{

map[i][j] = --idx;

find(i, j);

Area[nArea++] = nCount;

nCount = 0;

}

}

}

for (int i = 0; i < nArea-1; i++)

{

for (int j = 0; j < nArea - 1 -i; j++)

{

if (Area[j] > Area[j + 1])

{

int tmp = Area[j];

Area[j] = Area[j + 1];

Area[j + 1] = tmp;

}

}

}

printf("%d\n", nArea);

for (int i = 0; i < nArea; i++)

{

printf("%d ", Area[i]);

}

}