HDU 1430 魔板 搜索
转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
起始状态和目标状态都已确定，而且状态比较多，可以双向BFS搞定，不过需要记录路径，代码不好写，而且需要时间多。
从Amb的博文里学到了预处理，由于是8种颜色，而且可以确定，就可以通过置换，把起始状态转换成12345678，目标状态同时也置换。
对于起点12345678，进行BFS，到所有状态的路径。对于每一种询问直接查询即可。
HASH用的是康托展开
DBL，ORZ
#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[8];int val;}s,u,v;int fac[8]={1,1,2,6,24,120,720,5040};int pre[40321];char ope[40321];int get_hash(int *tmp){int ret=0;for(int i=0;i<8;i++){int cnt=0;for(int j=0;j<i;j++)if(tmp[j]>tmp[i])cnt++;ret+=cnt*fac[i];}return ret;}void change_a(int *tmp){for(int i=0;i<4;i++)swap(tmp[i],tmp[7-i]);}void change_b(int *tmp){int temp=tmp[3];for(int i=3;i>0;i--)tmp[i]=tmp[i-1];tmp[0]=temp;temp=tmp[4];for(int i=4;i<7;i++)tmp[i]=tmp[i+1];tmp[7]=temp;}void change_c(int *tmp){int temp=tmp[1];tmp[1]=tmp[6];tmp[6]=tmp[5];tmp[5]=tmp[2];tmp[2]=temp;}void bfs(){queue<Node>que;que.push(s);pre[s.val]=-2;while(!que.empty()){u=que.front();que.pop();for(int i=0;i<3;i++){v=u;if(i==0){change_a(v.a);v.val=get_hash(v.a);if(pre[v.val]==-1){ope[v.val]=i+'A';pre[v.val]=u.val;que.push(v);}}else if(i==1){change_b(v.a);v.val=get_hash(v.a);if(pre[v.val]==-1){ope[v.val]=i+'A';pre[v.val]=u.val;que.push(v);}}else{change_c(v.a);v.val=get_hash(v.a);if(pre[v.val]==-1){ope[v.val]=i+'A';pre[v.val]=u.val;que.push(v);}}}}}int main(){memset(pre,-1,sizeof(pre));int t[8]={1,2,3,4,5,6,7,8};memcpy(s.a,t,8*sizeof(int));s.val=get_hash(s.a);bfs();char s1[10],s2[10];while(scanf("%s%s",s1,s2)!=EOF){int pos[10];int des[8];for(int i=0;i<8;i++)pos[s1[i]-'0']=i+1;for(int i=0;i<8;i++)des[i]=pos[s2[i]-'0'];int tmp=get_hash(des),cnt=0;char ans[1000];while(pre[tmp]!=-2){ans[cnt++]=ope[tmp];tmp=pre[tmp];}for(int i=cnt-1;i>=0;i--)putchar(ans[i]);putchar('\n');}return 0;}