给九个格子1，2，...9  一共9个数组，每次只能交换9与他直接相邻的数字，计算从一种状态到另外一种状态的最少移动步数。

用广搜+康拓展开的方法实现。

#include "stdafx.h"

#include<iostream>

#include<string>

#include <vector>

#include <math.h>

#include <map>

#include <queue>

using namespace std;

const int MAX=400000;

long int fac[]={1,1,2,6,24,120,720,5040,40320,362880}; //表示阶乘运算的结果

//long int fac[]={0!,1!,2!,3!,4!,5!,6!,7!,8!,9!};

//康拓展开

int Cantor(int *s,int n)

{

int i,j,num,temp;

num=0;

for(i=0;i<n;i++)

{

temp=0; //temp记录当前数位前面的低数位中小于当前位数上的数字的个数

for(j=i+1;j<n;j++)

if(s[j]<s[i])

temp++;

num+=fac[n-1-i]*temp; //乘以相应的阶乘

}

return num;

}

//康拓展开逆运算

void CantorReverse(int index,int *p,int n)

{

//index--; //勿丢

int i,j;

bool hash[10]={0};

for(i=0;i<n;i++)

{

int tmp=index/fac[n-1-i]; //tmp表示有tmp个数字比当前位置上的数字小

for(j=0;j<=tmp;j++)

if(hash[j]) tmp++;

p[i]=tmp+1;

hash[tmp]=1;

index%=fac[n-1-i];

}

return;

}

//交换

int swapSquares(int index, int i, int j)

{

int s[10];

CantorReverse(index, s, 9);

int temp=s[i];

s[i]=s[j];

s[j]=temp;

index=Cantor(s, 9);

return index;

}

struct STATE{

int value;

int pos;

int step;

};

int bfs(STATE start, STATE end)

{

bool visited[MAX];//记录bfs是否扫描过

//每个状态可以到达的位置

char *neighbour[]={"13","024","15","046","1357","248","37","468","57"};

queue<STATE> Q;

Q.push(start);

while(!Q.empty())

{

STATE cur=Q.front();

Q.pop();

char *p=neighbour[cur.pos];

while(*p!='\0')

{

STATE tmp;

tmp.value = swapSquares(cur.value, cur.pos, *p-'0');

tmp.pos=*p-'0';

tmp.step=cur.step+1;

if(tmp.value == end.value)

return tmp.step;

if(visited[tmp.value] == false)

{

Q.push(tmp);

visited[tmp.value]=true;

}

p++;

}

}

return -1;

}

int main(int argc,char *argv)

{

int s1[10],s2[10];

STATE start, end;

start.step=0;

//输入开始状态

for (int i = 0; i< 9;i ++)

{

scanf("%d", &s1[i]);

if(s1[i]==9)

start.pos=i;

}

//输入结束状态

for (int i = 0; i< 9;i ++)

scanf("%d", &s2[i]);

start.value=Cantor(s1,9);

end.value=Cantor(s2,9);

if(start.value == end.value)

printf("%d\n",0);

else

printf("%d\n", bfs(start, end));

return 0;

}