http://acm.pku.edu.cn/JudgeOnline/problem?id=1077
Решение, базирующееся на двойном поиске в ширину:
Код:
#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; }