uva 10051 Tower of Cubes


标题:n個の六面体を与え、次にn行、各行に6個の数字があり、前、後、左、右、上、下の色を表す.各六面体の上から下への重量は増加した.重ね合わせのルールは六面体の上に必ず重さが小さいものを置くことです.また、接触する面の色は同じです.出力はいくつか重ねて、どちらを上に出力することができます.
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); }