点击打开链接
题意：
还是八数码，和1043相比， 这次给的是两个状态，一前一后。但这都不重要，重点是多了一个字典序，，，，，这真的难到我了。
题解：
A* 能快速找到最短的方法，但是不能确定字典序，gg。
后来我看了网上主要有两种解法，一种双向bfs （比较简单，但是我不明白这样找到的字典序的原理。）
第二种，就是与处理一下，X 放在任意位置都跑一边，路径存一下，依次递归就可以。（但是还是有样例会错误，但还是过了。）
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <algorithm> #include <cstdlib> #include <vector> #include <queue> const int maxn=370000; int hash_tab[maxn]; int a[10],b[10],v; char s1[10],s2[10]; int fn[11]; int dir[4][2]={1,0,0,-1,0,1,-1,0}; char way[]="dlru"; int op[11][maxn],ans[11][maxn]; using namespace std; struct node{ int x,y; int hash_val; char ma[3][3]; node(){}; node(char *s){ int xx=0,yy=0,len=strlen(s); for(int i=0;i<len;++i){ ma[xx][yy]=s[i]; if(s[i]=='X') x=xx,y=yy; ++yy; if(yy==3) ++xx,yy=0; } } }s,e,u; int get_hash(node a){ int i,j,k,cnt,ret = 0; int b[20]; for(i = 0; i<3; i++) { for(j = 0; j<3; j++) { b[3*i+j] = a.ma[i][j]; cnt = 0; for(k = 3*i+j-1; k>=0; k--) { if(b[k]>b[3*i+j]) cnt++; } ret+=fn[3*i+j]*cnt; } } return ret; } int judge(int x,int y){ if(x<0||x>2||y<0||y>2) return 0; return 1; } void bfs(int v){ memset(hash_tab,0,sizeof(hash_tab)); queue<node>que; s.hash_val=get_hash(s); que.push(s); hash_tab[s.hash_val]=1; while(!que.empty()){ e=que.front(); que.pop(); for(int i=0;i<4;++i){ int tx=e.x+dir[i][0]; int ty=e.y+dir[i][1]; if(!judge(tx,ty)) continue; u=e; u.x=tx,u.y=ty; u.ma[e.x][e.y]=u.ma[tx][ty]; u.ma[tx][ty]='X'; u.hash_val=get_hash(u); if(hash_tab[u.hash_val]) continue; hash_tab[u.hash_val]=1; op[v][u.hash_val]=e.hash_val; ans[v][u.hash_val]=way[i]; que.push(u); } } } int main(){ int n; memset(op[v],-1,sizeof(op)); fn[0]=1; for(int i=1;i<9;++i) fn[i]=i*fn[i-1]; s = node("X12345678"); bfs(0); s = node("1X2345678"); bfs(1); s = node("12X345678"); bfs(2); s = node("123X45678"); bfs(3); s = node("1234X5678"); bfs(4); s = node("12345X678"); bfs(5); s = node("123456X78"); bfs(6); s = node("1234567X8"); bfs(7); s = node("12345678X"); bfs(8); scanf("%d",&n); for(int ca=1;ca<=n;++ca){ scanf("%s %s",s1,s2); for(int i=0,j=0;i<9;++i) if(s1[i]=='X') v=i; else a[s1[i]-'0']=j++; for(int i=0,j=0;i<9;++i) if(s2[i]!='X') s2[i]=a[s2[i]-'0']+'1'; s=node(s2); int en=get_hash(s); string ss=""; while(en!=-1){ ss+=ans[v][en];//cout<<ans[v][en]<<endl; en=op[v][en]; } printf("Case %d: %d\n",ca,ss.size()-1); for(int i=ss.size()-2;i>=0;--i) printf("%c",ss[i]); puts(""); } return 0; }
