Отримання знань

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Примеры решения на C++:

   Решение, базирующееся на двойном поиске в ширину:

#include "iostream" 
#include "string.h" 
#include "map" 
using namespace std;
map < int,int > hasha,hashb;  
const int move[]={1,-1,3,-3}; 
int can[][9]={{1,1,0,1,1,0,1,1,0},{0,1,1,0,1,1,0,1,1},{1,1,1,1,1,1,0,0,0},{0,0,0,1,1,1,1,1,1}};
int nine[10],ak,sti,bk;
char sts[10]={0},status[10]={0},ch;
char ans[1001];
int st,stx,en,enx=8;
struct que
{
 int c,q;
 char s[10]; 
}qa[1000001],qb[1000001];
int ea,eb,ha,hb;
int atoi(char *s)
{
 int ret=0,i;
 for(i=0; i < 9; i++)ret+=(s[i]-'0')*nine[i];
 return ret; 
}
void bfs(int &a,int &b)
{
 int i;
 hasha.clear(),hashb.clear();
 ea=eb=2;ha=hb=1;
 hasha[st]=1,hashb[en]=1;
 strcpy(qa[ea].s,sts),qa[ea].c=stx,qa[ea].q=1;
 strcpy(qb[eb].s,"123456780"),qb[eb].c=enx,qb[eb].q=1;
 while(ea-ha || eb-hb)
 {
    if(ea-ha)
    {
     ha++;
     for(i=0; i < 4 ;i++)
     {
      if(!can[i][qa[ha].c]) continue;
      strcpy(status,qa[ha].s);
      status[qa[ha].c]=status[qa[ha].c+move[i]];
      status[qa[ha].c+move[i]]='0';
      sti=atoi(status);
      if(!hasha[sti])
      {
       ea++;
       hasha[sti]=ea;
       strcpy(qa[ea].s,status);
       qa[ea].c=qa[ha].c+move[i];
       qa[ea].q=ha;
       if(hashb[sti])
       {
        b=hashb[sti],a=ea;
        return;
       }
      }
     }
    }
    if(eb-hb)
    {
     hb++;
     for(i=0; i < 4; i++)
     {
      if(!can[i][qb[hb].c]) continue;
      strcpy(status,qb[hb].s);
      status[qb[hb].c]=status[qb[hb].c+move[i]];
      status[qb[hb].c+move[i]]='0';
      sti=atoi(status);
      if(!hashb[sti])
      {
       eb++;
       hashb[sti]=eb;
       strcpy(qb[eb].s,status);
       qb[eb].c=qb[hb].c+move[i];
       qb[eb].q=hb;
       if(hasha[sti])
       {
        a=hasha[sti],b=eb;
        return;
       }
      }
     }
    }
 }
}
char getccc(int cc)
{
 switch(cc)
 {
 case 1 : return 'r';
 case -1: return 'l';
 case 3 : return 'd';
 case -3: return 'u';
 }
}
void solve()
{
 int a,b;
 st=atoi(sts);
 if(en==st)return;
 bfs(a,b);
 ak=500,bk=501;
 while(a-1)
 {
    ans[ak--]=getccc(qa[a].c-qa[qa[a].q].c);
    a=qa[a].q;
 }
 while(b-1)
 {
    ans[bk++]=getccc(qb[qb[b].q].c-qb[b].c);
    b=qb[b].q;
 }
 ans[bk-1]=0;
 puts(ans+ak+2);
}
int main()
{
 int i,j,able=0;
 for(i=7,nine[8]=1; i >=0 ;i--)nine[i]=nine[i+1]*9;
 en=atoi("123456780");
 i=0;
 while( i< 9)
 {
    ch=getchar();
    if(isdigit(ch) ||ch=='x')
    {
     if(ch=='x')stx=i,ch='0';
     sts[i]=ch;
     i++;
    }
 }
 solve();
 return 0;
}

   Решение с использованием хеш-таблицы:

#include "stdio.h" 
#include "string.h" 
#define MAXN 362880
const int tar=123456789;
const int pw[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
const int jc[10]={1,1,2,6,24,120,720,5040,40320,362880};
int s , st[10] , que[MAXN][3] ;
char ch[50];
bool used[MAXN] ;

bool Isok(){
    int i , j , sum ;
    sum=0 ;
    for (i=1; i < 10; i++)
    for (j=i+1; j < 10; j++){
        if (st[i] > st[j])    sum++ ;    
    }
    if (sum%2==0)    return true ;
    return false ;
}
int Init(){
    int len , i , q , c=1;
    len=strlen(ch);
    s=0;
    for (i=0; i < len; i++){
        if ((ch[i] >= '0' && ch[i]<='9') || ch[i]=='x'){
            if (ch[i]=='x')        q=c , st[q]=10 ;
            else{
                if (s==0)    s=ch[i]-'0';
                else    s=s*10+ch[i]-'0' ;
                st[c]=ch[i]-'0' ;
                c++ ;        
            }    
        }    
    }    
    memset(used,0,sizeof(used));
    s=s*10+q ;
}

int Right(int a ){    return a+1 ;}
int Left (int a){    return a-1 ;}
int Up(int a ){
    int t1,t2,t3 ;
    t1=9-a%10+1 ;
    t2=a/pw[t1] ; 
    t3=t2/1000*1000+t2%100*10+t2/100%10 ;
    return t3*pw[t1]+a%pw[t1]/10*10+a%10-3 ;
}
int Down(int a ){
    int t1,t2,t3,t4;
    t1=9-a%10+1 ;    
    t2=a/pw[t1] ;
    t3=a%pw[t1];
    t4=(t3/pw[t1-2]+t3/pw[t1-3]%10*100)*pw[t1-3]+t3%pw[t1-3] ;
    return  t2*pw[t1]+t4/10*10+a%10+3 ;
}
int Hash(int a){
    int t[9] , i , j , k , res=0;
    for (i=0; i < 9; i++) {
        t[i]=a/pw[8-i]%10 ;    
    }
    for (i=0; i < 8; i++) {
        k=0 ;
        for (j=0; j < i; j++)
            if (t[i] < t[j]) k++ ;        
        res+=k*jc[i] ;
    }
    res+=(9-t[8])*jc[8] ;
    return res ;
}
int Solve() {
    int tmp , front ,rear ,i , tt;    
    que[0][0]=s ;
    tt=Hash(s);
    used[tt]=1 ;
    front=0 , rear=1 ;
    while(front < rear) {
        if (que[front][0] == tar)    break;
        tmp=(que[front][0]%10-1)%3 ;
        if (tmp < 2) {
            tmp=Right(que[front][0]);
            tt=Hash(tmp);
            if (!used[tt]) {
                used[tt]=1;
                que[rear][0]=tmp ;
                que[rear][1]=1 ;
                que[rear][2]=front ;
                rear++ ;
            }    
        }
        tmp=(que[front][0]%10-1)%3 ;
        if (tmp > 0) {
            tmp=Left(que[front][0]);
            tt=Hash(tmp);
            if (!used[tt]) {
                used[tt]=1;
                que[rear][0]=tmp ;
                que[rear][1]=2 ;
                que[rear][2]=front ;
                rear++ ;    
            }    
        }
        tmp=(que[front][0]%10-1)/3 ;
        if (tmp<2) {
            tmp=Down(que[front][0]);
            tt=Hash(tmp);
            if (!used[tt]) {
                used[tt]=1;
                que[rear][0]=tmp ;
                que[rear][1]=4 ;
                que[rear][2]=front ;
                rear++ ;  
            }    
        }
        tmp=(que[front][0]%10-1)/3 ;
        if (tmp > 0) {
            tmp=Up(que[front][0]);
            tt=Hash(tmp);
            if (!used[tt]) {
                used[tt]=1;
                que[rear][0]=tmp ;
                que[rear][1]=3 ;
                que[rear][2]=front ;
                rear++ ;    
            }    
        }
        front++;    
    }
    int stack[MAXN],top=0;
    rear=front;
    while (rear!=0) {
        stack[top++]=que[rear][1];
        rear=que[rear][2] ;    
    }
    for (i=top-1; i >= 0; i--) {
        switch(stack[i]) {
            case 1:putchar('r') ;    break;
            case 2:putchar('l') ; break;
            case 3:putchar('u') ; break;
            default:putchar('d');
        }    
    }
    printf(" ");
}

int main() {
    while (gets(ch)) {
        Init();    
        if(Isok()) {
            Solve();       
        }
        else    printf("unsolvable ");
    }
    return 0;    
}