반응형
https://www.algospot.com/judge/problem/read/DESIGNSCHOOL
algospot.com :: DESIGNSCHOOL
알고스팟 디자인 스쿨 문제 정보 문제 "Woojoo! Where have you been?" "What's the matter, teacher?" "I told you that the admissions information on Algospot Design School was out, and that you needed to prepare a portfolio for that. Did you fini
www.algospot.com
1. TIME_OVER
2. 모든 경우의 수를 탐색하는 백트래킹 방법으로는 해결이 불가함
3. 간선 그래프를 사용하여 해결하고자 함
#include<stdio.h>
typedef struct{
int bottom;
int left;
int top;
int right;
}RECT;
typedef struct{
int data[101];
int length;
}QUEUE;
RECT rect[101];
int L;
QUEUE aftQ;
int MAX;
int CRASH(RECT r1, RECT r2)
{
if ((r1.left < r2.right && r1.right > r2.left &&
r1.bottom < r2.top && r1.top > r2.bottom)
)
return 0;
return 1;
}
void func(int index)
{
int i;
if (aftQ.length + (L - index) <= MAX)
return;
for (i = 0; i < aftQ.length; i++){
if (!CRASH(rect[aftQ.data[i]], rect[index])){
return;
}
}
aftQ.data[aftQ.length++] = index;
for (i = index+1; i < L; i++){
func(i);
}
if (MAX < aftQ.length)
MAX = aftQ.length;
--aftQ.length;
return;
}
int main()
{
int T;
for (scanf("%d", &T); T > 0; T--)
{
int i;
MAX = -999;
aftQ.length = 0;
scanf("%d", &L);
for (i = 0;i<L; i++)
{
char C;
scanf("%d %d %d %d %c",
&rect[i].bottom,
&rect[i].left,
&rect[i].top,
&rect[i].right,
&C);
}
for (i = 0; i < L;i++)
func(i);
printf("%d\n", MAX);
}
return 0;
}
반응형