#include
#include
#include
using namespace std;
int mark;
int shift[9][9];//shift[0][1]表示x在1位置上的偏移
int factorial[9]={
1,1,2,6,24,120,720,5040,40320
};//factorial[3]=3!
struct maze{
int f,g,h;
int A[9];
int pos[200];//某个数(下标)的位置
int hash;
int prev;
int direction;
bool operator <(const maze &m1) const
{
return f>m1.f;
}
public:
maze(){};
int get_hash(){
int sum=0;
int temp;
for(int i=0;i
if(A[i]=='x'){
sum+=(9-i)*factorial[8];
continue;
}
temp=0;
for(int j=0;j
if(A[j]>A[i]&&A[j]!='x') temp++;
}
sum+=temp*factorial[i];
}
return sum;
}//康拓展开(n位全排列唯一)
maze(int temp[]){
for(int i=0;i<9;i++){
A[i]=temp[i];
pos[temp[i]]=i;
}
f=g=h=0;
for(int i=0;i<9;i++){
if(A[i]=='x') h+=shift[0][i];
else h+=shift[A[i]][i];
}
prev=-1;
hash=get_hash();
direction=-1;
}
void PrintItSelf(){
if(direction==0) cout<<"向上"<<endl;
else if(direction==1) cout<<"向下"<<endl;
else if(direction==2) cout<<"向左"<<endl;
else if (direction==3) cout<<"向右"<<endl;
for(int i=0;i<9;i++){
if(i%3==2){
if(A[i]!='x') cout<<A[i]<<endl;
else cout<<'x'<<endl;
}
else{
if(A[i]!='x') cout<<A[i]<<" ";
else cout<<'x'<<" ";
}
}
}
};
priority_queue openlist;
int vis[500000];
int dir[]={
-3,3,-1,1//上下左右
};
//int problem[]={2,8,3,1,6,4,7,'x',5};
//int target[]={1,2,3,8,'x',4,7,6,5};
// 2 8 3 1 6 4 7 x 5
// 1 2 3 8 x 4 7 6 5
int problem[9]={2,3,4,1,5,'x',7,6,8};
int target[9]={1,2,3,4,5,6,7,8,'x'};
maze M[500000];
void calculate(maze &m1){
if(m1.prev!=-1) m1.g=M[m1.prev].g+1;
m1.f=m1.g+m1.h;
}
int check(int m,int i){//判断此处是否在九宫格内
int row=m/3;
int col=m%3;
switch(i){
case 0:row--;break;
case 1:row++;break;
case 2:col--;break;
case 3:col++;break;
}
if(row>=0&&row<=2&&col>=0&&col<=2) return 1;
return 0;
}
void Astar(){
maze m1=maze(problem);
calculate(m1);
openlist.push(m1);
while(openlist.size()){
maze Temp=openlist.top();openlist.pop();
vis[Temp.hash]=1;
if(!Temp.h){//打印路径
int steps=Temp.f;
printf("第%d步\n",steps--);
Temp.PrintItSelf();
printf("\n");
int now=Temp.prev;
while(now!=-1){
if(steps==0) printf("初始状态 ",steps--);
else printf("第%d步 ",steps--);
M[now].PrintItSelf();
printf("\n");
now=M[now].prev;
}
break;
}
int m=Temp.pos['x'];//m是x的位置
for(int i=0;i<4;i++){
int p=m+dir[i];//p是待交换的位置
## if(p>=0&&p<=8){//最初使用的判断导致错误,但是用check函数却会报错
int B[9];
for(int k=0;k<9;k++) B[k]=Temp.A[k];
int mid=B[p];B[p]='x';B[m]=mid;
maze Pmaze=maze(B);
if(vis[Pmaze.hash]==1) continue;
else if(vis[Pmaze.hash]==0){
if(Temp.g+1<Pmaze.g){
Pmaze.g=Temp.g+1;
Pmaze.f=Pmaze.g+Pmaze.h;
Temp.direction=i;
M[mark]=Temp;
Pmaze.prev=mark++;
}
}
else{
Temp.direction=i;
M[mark]=Temp;
Pmaze.prev=mark++;
calculate(Pmaze);
openlist.push(Pmaze);
vis[Pmaze.hash]=0;
}
}
}
}
}
int verse(int a[9]){
int sum=0;
for(int i=0;i
if(a[i]=='x') continue;
for(int j=0;j
{
if(a[j]>a[i]&&a[j]!='x') sum++;
}
}
return sum%2;
}//逆序数奇偶性相同有解,不同无解
void ProcessShift(){
maze m1=maze(problem);
maze m2=maze(target);
int a=m2.pos['x']/3;
int b=m2.pos['x']%3;
for(int j=0;j<9;j++){
int row3=j/3;
int column3=j%3;
shift[0][j]=abs(a-row3)+abs(b-column3);
}
for(int i=1;i<9;i++){
int row1=m2.pos[i]/3;
int column1=m2.pos[i]%3;
for(int j=0;j<9;j++){
int row2=j/3;
int column2=j%3;
shift[i][j]=abs(row1-row2)+abs(column1-column2);
}
}
}//预处理偏移
int main(){
mark=0;//存储九宫格,用来打印路径
memset(vis,-1,sizeof(vis));
ProcessShift();
if(verse(problem)!=verse(target)) cout<<"无法解决"<<endl;
else Astar();
return 0;
}
最初使用的判断导致错误,
但是用check函数却会报错,百思不得其解!!