HDU 3567 Eight II 八数码（2）
转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
八数码的升级版，给定起点，终点，双向BFS可破。有了魔板那题的基础。
同样对这题进行预处理，不过需要注意的是，这题有不同的情况，也就是空位X造成的，所以枚举X的位置，9种置换，进行BFS。
对于每一种起点，保存所有的能到达状态的路径。
跑了近1S左右。HASH依旧是康托展开
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<cmath>#include<string>#include<vector>#include<algorithm>#include<map>#include<set>#define inf 1<<30#define LL long long#define maxn 1<<24using namespace std;struct Node{int a[3][3];int val;int x,y;bool check(){if(x>=0&&x<3&&y>=0&&y<3)return true;return false;}}tmp,u,v;int fac[3][3]={{1,1,2},{6,24,120},{720,5040,40320}};int pre[9][370000];char ope[9][370000];int way[4][2]={{1,0},{0,-1},{0,1},{-1,0}};bool flag[370000];int get_hash(int maze[3][3]){int ret=0;for(int i=0;i<3;i++)for(int j=0;j<3;j++){int cnt=0;for(int a=0;a<i;a++)for(int b=0;b<3;b++)if(maze[a][b]>maze[i][j])cnt++;for(int b=0;b<j;b++)if(maze[i][b]>maze[i][j])cnt++;ret+=cnt*fac[i][j];}return ret;}void bfs(int kind){queue<Node>que;que.push(tmp);pre[kind][tmp.val]=-2;flag[tmp.val]=true;while(!que.empty()){u=que.front();que.pop();for(int i=0;i<4;i++){v=u;v.x+=way[i][0];v.y+=way[i][1];if(v.check()){swap(v.a[v.x][v.y],v.a[u.x][u.y]);v.val=get_hash(v.a);if(pre[kind][v.val]==-1){flag[v.val]=true;pre[kind][v.val]=u.val;ope[kind][v.val]=i;que.push(v);}}}}}void Init(char *str,int kind){int k=0;for(int i=0;i<3;i++)for(int j=0;j<3;j++){if(str[k]=='X')tmp.a[i][j]=0;elsetmp.a[i][j]=str[k]-'0';k++;}tmp.x=kind/3;tmp.y=kind%3;tmp.val=get_hash(tmp.a);bfs(kind);}char ch[5]={"dlru"};int main(){memset(pre,-1,sizeof(pre));memset(flag,false,sizeof(flag));Init("X12345678",0);Init("1X2345678",1);Init("12X345678",2);Init("123X45678",3);Init("1234X5678",4);Init("12345X678",5);Init("123456X78",6);Init("1234567X8",7);Init("12345678X",8);int t,cas=0;scanf("%d",&t);while(t--){char s1[10],s2[10];scanf("%s%s",s1,s2);int a[3][3],b[3][3],pos,c[9],k=1;for(int i=0;i<9;i++){if(s1[i]=='X'){c[0]=0;pos=i;}elsec[s1[i]-'0']=k++;}for(int i=0;i<9;i++) b[i/3][i%3]=(s2[i]=='X'?c[0]:c[s2[i]-'0']);int temp=get_hash(b);int cnt=0,ans[1000];while(pre[pos][temp]!=-2){ans[cnt++]=ope[pos][temp];temp=pre[pos][temp];}printf("Case %d: %d\n",++cas,cnt);for(int i=cnt-1;i>=0;i--)printf("%c",ch[ans[i]]);printf("\n");}return 0;}