#include <stdio.h>
#define inf 1000000000
int R, C, H, N, d[8][8][8][8][8][8], grape[8][8][8][8][8][8];
void input(void)
{
int i, r, c, h;
scanf("%d %d %d %d",&R,&C,&H,&N);
for(i=1 ; i<=N ; i++)
{
scanf("%d %d %d",&r,&c,&h);
grape[r][r][c][c][h][h]=1;
}
}
void process(void)
{
int i, j, k, l, r1, r2, c1, c2, h1, h2;
for(i=1 ; i<=R ; i++)
for(j=1 ; j<=C ; j++)
for(k=1 ; k<=H ; k++)
for(r1=1 ; r1<=R-i+1 ; r1++)
{
r2=r1+i-1;
for(c1=1 ; c1<=C-j+1 ; c1++)
{
c2=c1+j-1;
for(h1=1 ; h1<=H-k+1 ; h1++)
{
h2=h1+k-1;
if(i>=2)
grape[r1][r2][c1][c2][h1][h2]=grape[r1][r2-1][c1][c2][h1][h2]+grape[r2][r2][c1][c2][h1][h2];
else if(j>=2)
grape[r1][r2][c1][c2][h1][h2]=grape[r1][r2][c1][c2-1][h1][h2]+grape[r1][r2][c2][c2][h1][h2];
else if(k>=2)
grape[r1][r2][c1][c2][h1][h2]=grape[r1][r2][c1][c2][h1][h2-1]+grape[r1][r2][c1][c2][h2][h2];
for(l=r1 ; l<=r2-1 ; l++)
{
if(grape[r1][l][c1][c2][h1][h2] && grape[l+1][r2][c1][c2][h1][h2])
{
if(!d[r1][r2][c1][c2][h1][h2] || d[r1][r2][c1][c2][h1][h2]>d[r1][l][c1][c2][h1][h2]+d[l+1][r2][c1][c2][h1][h2]+1)
d[r1][r2][c1][c2][h1][h2]=d[r1][l][c1][c2][h1][h2]+d[l+1][r2][c1][c2][h1][h2]+1;
}
else
if(!d[r1][r2][c1][c2][h1][h2] || d[r1][r2][c1][c2][h1][h2]>d[r1][l][c1][c2][h1][h2]+d[l+1][r2][c1][c2][h1][h2])
d[r1][r2][c1][c2][h1][h2]=d[r1][l][c1][c2][h1][h2]+d[l+1][r2][c1][c2][h1][h2];
}
for(l=c1 ; l<=c2-1 ; l++)
{
if(grape[r1][r2][c1][l][h1][h2] && grape[r1][r2][l+1][c2][h1][h2])
{
if(!d[r1][r2][c1][c2][h1][h2] || d[r1][r2][c1][c2][h1][h2]>d[r1][r2][c1][l][h1][h2]+d[r1][r2][l+1][c2][h1][h2]+1)
d[r1][r2][c1][c2][h1][h2]=d[r1][r2][c1][l][h1][h2]+d[r1][r2][l+1][c2][h1][h2]+1;
}
else
if(!d[r1][r2][c1][c2][h1][h2] || d[r1][r2][c1][c2][h1][h2]>d[r1][r2][c1][l][h1][h2]+d[r1][r2][l+1][c2][h1][h2])
d[r1][r2][c1][c2][h1][h2]=d[r1][r2][c1][l][h1][h2]+d[r1][r2][l+1][c2][h1][h2];
}
for(l=h1 ; l<=h2-1 ; l++)
{
if(grape[r1][r2][c1][c2][h1][l] && grape[r1][r2][c1][c2][l+1][h2])
{
if(!d[r1][r2][c1][c2][h1][h2] || d[r1][r2][c1][c2][h1][h2]>d[r1][r2][c1][c2][h1][l]+d[r1][r2][c1][c2][l+1][h2]+1)
d[r1][r2][c1][c2][h1][h2]=d[r1][r2][c1][c2][h1][l]+d[r1][r2][c1][c2][l+1][h2]+1;
}
else
if(!d[r1][r2][c1][c2][h1][h2] || d[r1][r2][c1][c2][h1][h2]>d[r1][r2][c1][c2][h1][l]+d[r1][r2][c1][c2][l+1][h2])
d[r1][r2][c1][c2][h1][h2]=d[r1][r2][c1][c2][h1][l]+d[r1][r2][c1][c2][l+1][h2];
}
}
}
}
}
void output(void)
{
printf("%d",d[1][R][1][C][1][H]);
}
int main(void)
{
input();
process();
output();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
3136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
