Source Code

Problem: 1872  User: yzhw 
Memory: 688K  Time: 32MS 
Language: G++  Result: Accepted 

Source Code 
# include <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
int map[11][11];
int next[6][6][5];
bool used[20000];
void init_next(int f,int u,int d,int l,int r,int extra)
{
   next[f][d][0]=u;
   next[f][d][1]=d;
   next[f][d][2]=l;
   next[f][d][3]=r;
   next[f][r][0]=l;
   next[f][r][1]=r;
   next[f][r][2]=d;
   next[f][r][3]=u;
   next[f][u][0]=d;
   next[f][u][1]=u;
   next[f][u][2]=r;
   next[f][u][3]=l;
   next[f][l][0]=r;
   next[f][l][1]=l;
   next[f][l][2]=u;
   next[f][l][3]=d;
   next[f][l][4]=next[f][r][4]=next[f][u][4]=next[f][d][4]=extra;
}
void decode(int code,int &r,int &c,int &now,int &front)
{
   front=(code&7);
   code>>=3;
   now=code&7;
   code>>=3;
   c=code&15;
   code>>=4;
   r=code&15;
}
int encode(int r,int c,int now,int front)
{
    int code=r;
    code<<=4;
    code|=c;
    code<<=3;
    code|=now;
    code<<=3;
    code|=front;
    return code;
}
int row,col,sr,sc;
int refer[20000][2],res=0xfffffff,trefer[20000][2];
void dfs(int level,int code)
{
   
   int r,c,now,front;
   decode(code,r,c,now,front);
   if(r==sr&&c==sc&&level>1)
   {
      if(level<res) 
      {
         res=level;
         trefer[level][0]=r;
         trefer[level][1]=c;
         for(int i=0;i<=level;i++)
            refer[i][0]=trefer[i][0],refer[i][1]=trefer[i][1];
      }
      return;
   }
   if(used[code]) return;
   if(level>res) return;
   //printf("level=%d r=%d c=%d now=%d front=%d\n",level,r,c,now+1,front+1);
   //system("pause");
   trefer[level][0]=r,trefer[level][1]=c;
   used[code]=1;
   if(r>1&&(map[r-1][c]==-1||map[r-1][c]==now+1))
      dfs(level+1,encode(r-1,c,next[now][front][1],next[now][front][4]));
   if(r<row&&(map[r+1][c]==-1||map[r+1][c]==now+1))
      dfs(level+1,encode(r+1,c,next[now][front][0],now));
   if(c>1&&(map[r][c-1]==-1||map[r][c-1]==now+1))
      dfs(level+1,encode(r,c-1,next[now][front][3],front));
   if(c<col&&(map[r][c+1]==-1||map[r][c+1]==now+1))
      dfs(level+1,encode(r,c+1,next[now][front][2],front));
   used[code]=0;
}
int main()
{   
    init_next(0,2,3,4,1,5);
    init_next(1,2,3,0,5,4);
    init_next(2,0,5,1,4,3);
    init_next(3,5,0,1,4,2);
    init_next(4,2,3,5,0,1);
    init_next(5,2,3,1,4,0);
    while(true)
    {
       char name[30];
       int now,front;
       scanf("%s",name);
       if(!strcmp(name,"END")) break;
       scanf("%d %d %d %d %d %d",&row,&col,&sr,&sc,&now,&front);
      // memset(map,0,sizeof(map));
       for(int i=1;i<=row;i++)
         for(int j=1;j<=col;j++)
           scanf("%d",&map[i][j]);
       memset(used,0,sizeof(used));
       res=0xfffffff;
       dfs(0,encode(sr,sc,now-1,front-1));
       printf("%s\n",name);
       if(res==0xfffffff)
         printf("  No Solution Possible\n");
       else
       {
         printf("  ");
         for(int i=0;i<=res;i++)
         {
            if(i==res)
              printf("(%d,%d)\n",refer[i][0],refer[i][1]);
            else
              printf("(%d,%d),",refer[i][0],refer[i][1]);
            if(i%9==8&&i!=res)
               printf("\n  ");
         }
       }
    }
    return 0;
}