瞻仰下八數碼，可惜效率還不行啊，看到那么多0MS的，打擊啊。。。這題如果要0MS，必須是A*吧，呵呵 可惜還不會呀。。。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct node
{
int dir;
int pre;
int step;
char x[10];
}l[400000];
char x[15];
char ansx[15]="123456780";
int perm[] = {1,1,2,6,24,120,720,5040,40320};//n！
int d[] = {-1,-3, 1, 3};//四個方向的下標變換,左上右下。
bool move[][4] = {0,0,1,1, 1,0,1,1, 1,0,0,1, 0,1,1,1, 1,1,1,1, 1,1,0,1, 0,1,1,0, 1,1,1,0, 1,1,0,0};
//各個位置的可行變換
int v[362881];//數組判重
int hash()//用逆序數和變進制進行hash
{
int h = 0;
for(int i = 1;i<9;i++)
{
int count = 0;
for(int j=0;j<i;j++)
if(x[j] > x[i])count ++;
h += count * perm[i];
}
return h;
}
void input()
{
char t[5];
for(int i=0;i<9;i++)
{
scanf("%s",t);
x[i]=t[0];
if(x[i]=='x')
x[i]='0';
}
}
int pos;
void search(char x[])
{
for(int i=0;i<9;i++)
if(x[i]=='0')
{
pos=i;
break;
}
}
char ans[4000000]={0};
void GetDir(int h)
{
memset(ans,0,sizeof(ans));
int i;
int n=l[h].step;
for(i=n;i>=1;i--)
{
if(l[h].dir==0)
ans[i]='l';
else if(l[h].dir==1)
ans[i]='u';
else if(l[h].dir==2)
ans[i]='r';
else if(l[h].dir==3)
ans[i]='d';
h=l[h].pre;
}
}
int main()
{
int head,tail;
memset(v,0,sizeof(int)*362881);
head=tail=1;
input();
//
int code=hash();
v[code]=1;
l[head].step=0;
l[head].pre=-1;
strcpy(l[head].x,x);
//initial
while(head<=tail)
{
if(strcmp(l[head].x,ansx)==0)
break;//此時head為所求解
search(l[head].x);
for(int i=0;i<4;i++)
{
if(move[pos][i]==0)
continue;
strcpy(x,l[head].x);
int np=pos+d[i];
swap(x[pos],x[np]);
int code=hash();
if(!v[code])
{
tail++;
v[code]=1;
l[tail].step=l[head].step+1;
l[tail].pre=head;
l[tail].dir=i;
strcpy(l[tail].x,x);
}
}
head++;
}
if(head>tail)
printf("unsolvable\n");
else
{
GetDir(head);
printf("%s\n",ans+1);
}
return 0;
}
另外那個十五數碼，能用程序搞出來么？
這里的哈希函數是用能對許多全排列問題適用的方法。取n!為基數，狀態第n位的逆序值為哈希值第n位數。對于空格，取其（9-位置）再乘以8!。例如，1 3 7 2 4 6 8 5 8 的哈希值等于：
0*0! + 0*1! + 0*2! + 2*3! + 1*4! + 1*5! + 0*6! + 3*7! + (9-8)*8! = 55596 <9!
具體的原因可以去查查一些數學書，其中1 2 3 4 5 6 7 8 9 的哈希值是0 最小，8 7 6 5 4 3 2 1 0 的哈希值是（9!-1）最大，而其他值都在0 到 （9!-1） 中，且均唯一。