Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on May 21st, 2012  |  syntax: None  |  size: 2.86 KB  |  hits: 15  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include<stdio.h>
  2. #include<memory.h>
  3. #include<map>
  4. #include<string>
  5. #include<time.h>
  6. using namespace std;
  7.  
  8. int l[363000][9],ln,cr[9];
  9. void setall(int p)
  10. {
  11.         int i;
  12.         if(p==9)
  13.         {
  14.                 for(i=0;i<9;i++)
  15.                 {
  16.                         l[ln][cr[i]]=i;
  17.                 }
  18.                 ln++;
  19.         }
  20.         else
  21.         {
  22.                 for(i=0;i<9;i++)
  23.                 {
  24.                         if(cr[i]==-1)
  25.                         {
  26.                                 cr[i]=p;
  27.                                 setall(p+1);
  28.                                 cr[i]=-1;
  29.                         }
  30.                 }
  31.         }
  32. }
  33. int search(int C[9])
  34. {
  35.         int i,L,R,md,ll,rr;
  36.         ll=0;
  37.         rr=ln-1;
  38.         for(i=0;i<9;i++)
  39.         {
  40.                 L=ll;
  41.                 R=rr;
  42.                 while(L<=R)
  43.                 {
  44.                         md=(L+R)/2;
  45.                         if(l[md][i]<C[i])
  46.                         {
  47.                                 L=md+1;
  48.                         }
  49.                         else
  50.                         {
  51.                                 if(l[md][i]==C[i])
  52.                                 {
  53.                                         ll=md;
  54.                                 }
  55.                                 R=md-1;
  56.                         }
  57.                 }
  58.                 L=ll;
  59.                 R=rr;
  60.                 while(L<=R)
  61.                 {
  62.                         md=(L+R)/2;
  63.                         if(l[md][i]<=C[i])
  64.                         {
  65.                                 if(l[md][i]==C[i])
  66.                                 {
  67.                                         rr=md;
  68.                                 }
  69.                                 L=md+1;
  70.                         }
  71.                         else
  72.                         {
  73.                                 R=md-1;
  74.                         }
  75.                 }
  76.         }
  77.         return ll;
  78. }
  79. int q[400000][9];
  80. int d[400000];
  81. int h[400000],h2[400000];
  82. void run(int start[9])
  83. {
  84.         int bot,top,tmp,i,j,cur[9],cc;
  85.         bot=0;top=1;
  86.         for(i=0;i<9;i++)
  87.         {
  88.                 q[0][i]=start[i];
  89.         }
  90.         d[search(start)]=0;
  91.         while(bot<top)
  92.         {
  93.                 for(i=0;i<9;i++)
  94.                 {
  95.                         cur[i]=q[bot][i];
  96.                 }
  97.                 bot++;
  98.                 cc=search(cur);
  99.                 if(cc==0)break;
  100.                 for(i=0;i<9;i++)
  101.                 {
  102.                         if(cur[i]==8)break;
  103.                 }
  104.                 if(i>=3)
  105.                 {
  106.                         tmp=cur[i];
  107.                         cur[i]=cur[i-3];
  108.                         cur[i-3]=tmp;
  109.                         tmp=search(cur);
  110.                         if(d[tmp]==-1)
  111.                         {
  112.                                 d[tmp]=d[cc]+1;
  113.                                 h[tmp]=1;
  114.                                 h2[tmp]=cc;
  115.                                 for(j=0;j<9;j++)
  116.                                 q[top][j]=cur[j];
  117.                                 top++;
  118.                         }
  119.  
  120.                         tmp=cur[i];
  121.                         cur[i]=cur[i-3];
  122.                         cur[i-3]=tmp;
  123.                 }
  124.                 if(i<=5)
  125.                 {
  126.                         tmp=cur[i];
  127.                         cur[i]=cur[i+3];
  128.                         cur[i+3]=tmp;
  129.                         tmp=search(cur);
  130.                         if(d[tmp]==-1)
  131.                         {
  132.                                 d[tmp]=d[cc]+1;
  133.                                 h[tmp]=2;
  134.                                 h2[tmp]=cc;
  135.                                 for(j=0;j<9;j++)
  136.                                 q[top][j]=cur[j];
  137.                                 top++;
  138.                         }
  139.  
  140.                         tmp=cur[i];
  141.                         cur[i]=cur[i+3];
  142.                         cur[i+3]=tmp;
  143.                 }
  144.                 if(i%3>0)
  145.                 {
  146.                         tmp=cur[i];
  147.                         cur[i]=cur[i-1];
  148.                         cur[i-1]=tmp;
  149.                         tmp=search(cur);
  150.                         if(d[tmp]==-1)
  151.                         {
  152.                                 d[tmp]=d[cc]+1;
  153.                                 h[tmp]=3;
  154.                                 h2[tmp]=cc;
  155.                                 for(j=0;j<9;j++)
  156.                                 q[top][j]=cur[j];
  157.                                 top++;
  158.                         }
  159.  
  160.                         tmp=cur[i];
  161.                         cur[i]=cur[i-1];
  162.                         cur[i-1]=tmp;
  163.                 }
  164.                 if(i%3<2)
  165.                 {
  166.                         tmp=cur[i];
  167.                         cur[i]=cur[i+1];
  168.                         cur[i+1]=tmp;
  169.                         tmp=search(cur);
  170.                         if(d[tmp]==-1)
  171.                         {
  172.                                 d[tmp]=d[cc]+1;
  173.                                 h[tmp]=4;
  174.                                 h2[tmp]=cc;
  175.                                 for(j=0;j<9;j++)
  176.                                 q[top][j]=cur[j];
  177.                                 top++;
  178.                         }
  179.  
  180.                         tmp=cur[i];
  181.                         cur[i]=cur[i+1];
  182.                         cur[i+1]=tmp;
  183.                 }
  184.         }
  185. }
  186. char ans[1000];
  187. int main()
  188. {
  189.         int i,j,start[9];
  190.         char ch[3],ddd[5]="udlr";
  191. //      freopen("input.txt","r",stdin);
  192.         memset(cr,-1,sizeof(cr));
  193.         setall(0);
  194.         for(i=0;i<9;i++)
  195.         {
  196.                 scanf("%s",ch);
  197.                 if(ch[0]=='x')
  198.                         ch[0]='9';
  199.                 start[i]=ch[0]-'1';
  200.  
  201.         }
  202.         memset(d,-1,sizeof(d));
  203.         memset(h,-1,sizeof(h));
  204.         run(start);
  205.         i=j=0;
  206.         while(h[i]!=-1)
  207.         {
  208.                 ans[j++]=ddd[h[i]-1];
  209.                 i=h2[i];
  210.         }
  211.         ans[j]=0;
  212.         for(i=j-1;i>=0;i--)
  213.                 printf("%c",ans[i]);
  214.         printf("\n");
  215.         return 0;
  216. }
create a new version of this paste RAW Paste Data