#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
struct node{
int num[9];
int deepth;
int diffnum;
int value;
node *parent;
bool operator==(node *p){
int i;
for(i=0;i<sizeof(num)/sizeof(int);i++){
if(num[i]!=p->num[i]) return false;
}
return true;
}
} ;
bool cmp(node *a,node *b){
return a->value<b->value;}
class AStar{
public:
int start[9];
int target[9];
list<node*>openlist,closelist;
AStar(int start[],int target[]);
int findblank(int num[]);
int move_up(int num[]);
int move_down(int num[]);
int move_left(int num[]);
int move_right(int num[]);
bool isExisted(list<node*>tolist,node *p);
int diffnum(int num[]);
int expand(node *p);
int operate(int num[],int op);
void print_num(int num[]);
int print_result(node *p);
};
AStar::AStar(int start[],int target[]){
int i;
for(i=0;i<9;i++){
this->start[i]=start[i];
this->target[i]=target[i];
}
}
int AStar::findblank(int num[]){
int i;
for(i=0;i<9;i++)
if(num[i]==0) {return i;}
}
int AStar::move_up(int num[]){
int blank_pos=findblank(num);
if (blank_pos>2) {
swap(num[blank_pos],num[blank_pos-3]);
return 1;}
return 0;
}
int AStar::move_down(int num[]){
int blank_pos=findblank(num);
if(blank_pos<6){
swap(num[blank_pos],num[blank_pos+3]);
return 1;
}
return 0;
}
int AStar::move_left(int num[]){
int blank_pos=findblank(num);
if(blank_pos!=0&&blank_pos!=3&&blank_pos!=6){
swap(num[blank_pos],num[blank_pos-1]);
return 1;
}
return 0;
}
int AStar::move_right(int num[]){
int blank_pos=findblank(num);
if(blank_pos!=2&&blank_pos!=5&&blank_pos!=8){
swap(num[blank_pos],num[blank_pos+1]);
return 1;
}
return 0;
}
int AStar::operate(int num[],int op){
switch(op){
case 1:move_up(num);break;
case 2:move_down(num);break;
case 3:move_left(num);break;
case 4:move_right(num);break;
default:return 0;
}
}
bool AStar::isExisted(list<node*>tolist,node *isE){
list<node*>::iterator it;
it=find(tolist.begin(),tolist.end(),isE);
if(it!=tolist.end()) return true;
return false;
}
int AStar::diffnum(int num[]){
int i,count=0;
for(i=0;i<9;i++)
if(num[i]!=target[i]) count++;
return count;
}
int AStar::expand(node *p){
node *p1;
int i,op;
for(op=1;op<=4;op++){
p1=new node;
for(i=0;i<9;i++)
(p1->num)[i]=(p->num)[i];
p1->deepth=p->deepth;
p1->diffnum=p->diffnum;
p1->value=p->value;
p1->parent=NULL;
operate(p1->num,op);
if(isExisted(openlist,p1)==false&&isExisted(closelist,p1)==false){
p1->parent=p;
p1->deepth=p1->deepth+1;
p1->diffnum=diffnum(p1->num);
p1->value=p1->deepth+p1->diffnum;
if(p1->diffnum==0) {
int total=print_result(p1);
cout<<"all:"<<total<<endl;
return 1;
}
else openlist.push_back(p1);}
else delete p1;
}
return 0;
}
void AStar::print_num(int num[]){
int i;
for(i=0;i<9;i++){
cout<<num[i]<<"\t";
if((i%3)==2) cout<<endl;
}
}
int AStar::print_result(node *p){
int step;
if(p!=NULL){
step=print_result(p->parent);
cout<<step+1<<endl;
print_num(p->num);
return step+1;
}
else return -1;
}
int main(){
int start[9]={2,8,3,1,6,4,7,0,5};
int target[]={1,2,3,8,0,4,7,6,5};
AStar star(start,target);
node *p=new node;
p->parent=NULL;
p->deepth=0;
int i;
for(i=0;i<9;i++)
(p->num)[i]=start[i];
while(p!=NULL){
(star.closelist).push_front(p);
if(star.expand(p)) return EXIT_SUCCESS;
(star.openlist).sort(cmp);
p=(star.openlist).front();
(star.openlist).pop_front();
}
cout<<"No"<<endl;
}