-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbox max height
63 lines (54 loc) · 971 Bytes
/
box max height
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#define MAX 20
using namespace std;
int x[MAX],y[MAX];
int a[MAX][MAX]={0};
int queue[100];
int front,rear;
int in_degree[MAX]={0};
int dist[MAX]={0};
void find_max_height(){
int i,v;
front=-1;
rear=-1;
for(i=0;i<MAX;i++){
if(in_degree[i]==0){
queue[++rear] =i;
}
}
while(rear!=front){
v=queue[++front];
for(i=0;i<MAX;i++){
if(a[v][i]!=0 && in_degree[i]!=0){
if(dist[i]<dist[v]+a[v][i]) dist[i]=dist[v]+a[v][i];
in_degree[i]--;
if(in_degree[i]==0) queue[++rear]=i;
}
}
}
}
int main(){
int i,j;
int max=0;
for(i=0;i<MAX;i++){
cout<<"["<<i+1<<"] : ";
cin>>x[i]>>y[i];
}
for(i=0;i<MAX;i++){
for(j=i+1;j<MAX;j++){
if(x[i]>=x[j] && y[i]>=y[j]){
a[i][j]=1;
in_degree[j]++;
}
else if(x[i]<=x[j] && y[i]<=y[j]) {
a[j][i]=1;
in_degree[i]++;
}
}
}
find_max_height();
for(i=0;i<MAX;i++){
if(dist[i]>max) max=dist[i];
}
cout<<"최고높이: "<<max+1<<endl;
}