http://poj.org/problem?id=1077
题目的意思，就是通过不停的移动空格，把开始的状态转化成目的状态12345678x
目前能力只是到简单的单向bfs，还看了全排列的hash函数
总的求解流程
1.把开始结点压入队。 2.把开始结点状态写入哈希表 3.出队，访问结点。 4.创建结点的子结点，检查是否为目标状态。若是，搜索结束，若否，检查哈希表是否存在此状态。若已有此状态，跳过，若无，把此结点压入队。 重复3，4步骤，即可得解。 最后，我们根据目标状态结点回溯其父节点，可以得到完整的路径。
/* PKUoj Source Code Problem: 1077 User: 297752873 Memory: 6728K Time: 313MS Language: C Result: Accepted Source Code */ #include<stdio.h> #include<stdlib.h> #include<string.h> #define QueueSize 370000 int f[8] = {1, 2, 6, 24, 120, 720, 5040, 40320};//用于全排列的哈希函数的构建 char begin[10],end[10]={"123456780"};//开始和结束的状态 int beginf,endl,ans[400000],hash[400000];//开始和结束的点 struct eight { char str[10];//结点矩阵 int k ;//空格的位置 int fx;//移动的方向1表示上，2表示下, 3表示左，4表示右 int fa;//父节点 }s[370000]; typedef struct { int front; int rear; int count; int data[370000]; }CirQueue; CirQueue Q;//使用队列，队列里保存的是各状态的下标 void InitQueue(CirQueue *Q)//建队 { Q->front=Q->rear=0; Q->count=0; } int QueueEmpty(CirQueue *Q)//判队是否空 { return Q->count==0; } void EnQueue(CirQueue *Q,int x)//入队 { Q->count++; Q->data[Q->rear]=x; Q->rear=(Q->rear+1)%QueueSize; } int DeQueue(CirQueue *Q)//出队，并删除队首元素 { int temp; temp=Q->data[Q->front]; Q->count--; Q->front=(Q->front+1)%QueueSize; return temp; } int get_hash_code(char str[]) //计算全排列哈希值 { int i, j; int ret = 0, cnt; for(i = 1; i < 9; ++i) { cnt = 0; for(j = 0; j < i; ++j) if(str[j] > str[i]) cnt++; ret += cnt*f[i-1]; } return ret; } void print(int x)//若发现可完成，则利用父节点逐个输出 { int top; //printf("find "); top=0; while (x!=s[x].fa) { top++; ans[top]=s[x].fx; x=s[x].fa; } while (top!=0) { switch (ans[top]) { case 1:printf("u");break; case 2:printf("d");break; case 3:printf("l");break; case 4:printf("r");break; default:break; } top--; } printf(" "); } int bfs() { int w,k,has; char temp,a[10];//这些作为中间量 memset(hash,0,sizeof(hash)); InitQueue(&Q); if(strcmp(s[beginf].str,end)==0) { printf("lr "); return 0; } EnQueue(&Q,beginf); has=get_hash_code(s[beginf].str); hash[has]=1;//哈希表赋值 while(!QueueEmpty(&Q)) { w=DeQueue(&Q);//取队首元素 if(strcmp(s[w].str,end)==0) { print(w); return 0; } strcpy(a,s[w].str); k=s[w].k;//保留空格的位置 if (k>=3)//可上移的 { temp=a[k];a[k]=a[k-3];a[k-3]=temp; has=get_hash_code(a); if (hash[has]==0) { beginf++; strcpy(s[beginf].str,a); s[beginf].fx=1; s[beginf].fa=w; s[beginf].k=k-3; hash[has]=1; EnQueue(&Q,beginf); } temp=a[k];a[k]=a[k-3];a[k-3]=temp;//复原成原来的样子，以便下一个移动可以使用 } if (k%3!=0)//可左移的 { temp=a[k];a[k]=a[k-1];a[k-1]=temp; has=get_hash_code(a); if (hash[has]==0) { beginf++; strcpy(s[beginf].str,a); s[beginf].fx=3; s[beginf].fa=w; s[beginf].k=k-1; hash[has]=1; EnQueue(&Q,beginf); } temp=a[k];a[k]=a[k-1];a[k-1]=temp; } if (k%3!=2)//可右移的 { temp=a[k];a[k]=a[k+1];a[k+1]=temp; has=get_hash_code(a); if (hash[has]==0) { beginf++; strcpy(s[beginf].str,a); s[beginf].fx=4; s[beginf].fa=w; s[beginf].k=k+1; hash[has]=1; EnQueue(&Q,beginf); } temp=a[k];a[k]=a[k+1];a[k+1]=temp; } if (k<6)//可下移的 { temp=a[k];a[k]=a[k+3];a[k+3]=temp; has=get_hash_code(a); if (hash[has]==0) { beginf++; strcpy(s[beginf].str,a); s[beginf].fx=2; s[beginf].fa=w; s[beginf].k=k+3; hash[has]=1; EnQueue(&Q,beginf); }temp=a[k];a[k]=a[k+3];a[k+3]=temp; } } return 1; } int main() { int i,m,j; gets(begin); j=0; for(i=0;i<strlen(begin);i++){ if(begin[i]==' ')continue; if(begin[i]=='x') { begin[j]='0'; m=j; j++; }else begin[j++]=begin[i]; } begin[j]=' '; //printf("%s ",begin); beginf=0; s[beginf].fa=beginf;//第一个的父节点赋为自己 strcpy(s[beginf].str,begin); s[beginf].k=m; m=bfs(); if(m) printf("unsolvable "); return 0; }