背景 Background
Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们.
描述 Description
在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字.棋盘中留有一个空格,空格用0来表示.空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为123804765),找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入格式 Input Format
输入初试状态，一行九个数字，空格用0表示
输出格式 Output Format
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
样例输入 Sample Input
283104765
样例输出 Sample Output
4
分析：
BFS+康托展开。
数据结构定义：
dir：每个数字交换的方向(位置)。
zeropos：0的位置,枚举了0的位置再根据交换的方向确定与0交换的那个数字的位置。
numpos：读入的一维数字的二维坐标，也是方面zeropos好计算而设定的。
最后就是把BFS框架打出来，中间加上个康托展开=AC。
ps：pascal爱好者的数组和c++的是不同的哦，注意!
【参考程序】：
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
const int dir[4][2]={{-1,0},{0,-1},{0,1},{1,0}};
const int zeropos[9][2]={
{0,0},{0,1},{0,2},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2}};
const int numpos[3][3]={{0,1,2},{3,4,5},{6,7,8}};
struct node
{
int dep;
char s[10];
} list[100010];
bool hash[362890];
int F[9];
int hashs;
char st[10],goal[10];
int kang(char *str)
{
int a[10],bo[10];
int k,len,p,s;
len=strlen(str);
for (int i=0;i<len;i++) a[i+1]=(str[i]-'0')+1;
memset(bo,false,sizeof(bo));
s=1; k=8;
for (int i=1;i<=9;i++,k--)
{
bo[a[i]]=true;
p=0;
for (int j=1;j<=a[i]-1;j++)
if (!bo[j]) p++;
s+=F[k]*p;
}
return s;
}
void bfs()
{
int head,tail,xx,yy,x,y,zero,temp,len;
char ch,st2[10];
head=tail=1;
strcpy(list[1].s,st); list[1].dep=0;
while (head<=tail)
{
len=strlen(list[head].s);
for (int i=0;i<len;i++)
if (list[head].s[i]=='0')
{
zero=i; break;
}
x=zeropos[zero][0]; y=zeropos[zero][1];
for (int i=0;i<=3;i++)
{
xx=x+dir[i][0]; yy=y+dir[i][1];
if (xx>=0 && xx<=2 && yy>=0 && yy<=2)
{
temp=numpos[xx][yy];
strcpy(st2,list[head].s);
ch=st2[temp]; st2[temp]=st2[zero]; st2[zero]=ch;
temp=kang(st2);
if (!hash[temp])
{
hash[temp]=true;
tail++;
strcpy(list[tail].s,st2);
list[tail].dep=list[head].dep+1;
}
if (temp==hashs)
{
tail++;
strcpy(list[tail].s,st2);
list[tail].dep=list[head].dep+1;
printf("%d\n",list[tail].dep);
return ;
}
}
}
head++;
}
}
int main()
{
F[0]=1;
for (int i=1;i<=8;i++) F[i]=F[i-1]*i;
scanf("%s",st);
memset(hash,false,sizeof(hash));
strcpy(goal,"123804765");
hashs=kang(goal);
hash[hashs]=true;
hash[kang(st)]=true;
bfs();
return 0;
}