uva 10051 Tower of Cubes
标题:n個の六面体を与え、次にn行、各行に6個の数字があり、前、後、左、右、上、下の色を表す.各六面体の上から下への重量は増加した.重ね合わせのルールは六面体の上に必ず重さが小さいものを置くことです.また、接触する面の色は同じです.出力はいくつか重ねて、どちらを上に出力することができます.
map[i][j]は、i番目の六面体jが上向きに向かう最大高さとして定義される.構造体routeでパスを保存します.
map[i][j]は、i番目の六面体jが上向きに向かう最大高さとして定義される.構造体routeでパスを保存します.
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=505;
int n,map[N][10],change[6]={1,0,3,2,5,4};
bool vis[N][10];
int dp(int,int);
void print_ans(int,int,int);
struct ROUTE
{
int x,y;
void fun(int a,int b){x=a;y=b;}
}route[N][6];
struct node
{
int face[6],weight;
void fun(int a,int b,int c,int d,int e,int f,int h)
{
face[0]=a;face[1]=b;face[2]=c;face[3]=d;
face[4]=e;face[5]=f;weight=h;
}
}cube[N];
int main()
{
int t_cnt=0;
while(scanf("%d",&n)!=EOF)
{
if(n==0) break;
memset(map,0,sizeof(map));
memset(route,0,sizeof(route));
memset(vis,0,sizeof(vis));
int imax=0,x,y;
for(int i=0;i<n;i++)
{
int a,b,c,d,e,f;
scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
cube[i].fun(a,b,c,d,e,f,i+1);
}
for(int i=0;i<n;i++)
{
for(int j=0;j<6;j++)
{
int temp=dp(i,j);
if(imax<temp)
{
imax=temp;x=i;y=j;
}
}
}
if(t_cnt!=0) puts("");
printf("Case #%d
%d
",++t_cnt,imax);
print_ans(x,y,imax);
}
return 0;
}
int dp(int x,int y)
{
if(vis[x][y]) return map[x][y];
else
{
for(int i=x+1;i<n;i++)
{
for(int j=0;j<6;j++)
{
if(cube[x].face[change[y]]==cube[i].face[j])
{
int temp=dp(i,j)+1;
if(temp>map[x][y])
{
map[x][y]=temp;
route[x][y].fun(i,j);
}
}
}
}
vis[x][y]=1;
map[x][y]=max(map[x][y],1);
return map[x][y];
}
}
void print_ans(int x,int y,int cnt)
{
printf("%d ",x+1);
if(y==0) puts("front");
else if(y==1) puts("back");
else if(y==2) puts("left");
else if(y==3) puts("right");
else if(y==4) puts("top");
else puts("bottom");
if(cnt==1) return;
else print_ans(route[x][y].x,route[x][y].y,cnt-1);
}