#include<iostream>
#include<queue>
using namespace std;
const int SIZE=3;
class node
{
public:
int a[SIZE][SIZE];
int x;
int y;
node* up,*down,*right,*left,*parent;
node()
{
x=y=0;
parent=left=up=down=right=NULL;
}
void arrTo(int ar[SIZE][SIZE])
{
int i,j;
for(i=0;i<SIZE;i++){
for(j=0;j<SIZE;j++){
this->a[i][j]=ar[i][j];
}
}
}
bool IsGoal()
{
int i,j,val=1;
for(i=0;i<SIZE;i++){
for(j=0;j<SIZE;j++){
if(a[i][j]!=(val%(SIZE*SIZE)))
return false;
val=(val%(SIZE*SIZE))+1;
}
}
return true;
}
void Show(){
int i,j;
for(i=0;i<SIZE;i++){
for(j=0;j<SIZE;j++){
cout.width(3);
cout<<a[i][j];
}
cout<<endl;
}
}
static void Delete(node* root)
{
if(root!=NULL){
Delete(root->up);
Delete(root->down);
Delete(root->left);
Delete(root->right);
delete root;
}
}
};
int main()
{
int a[][SIZE]={ {7,3,8},
{5,4,6},
{1,2,0}};
int height=1,steps=1,i,j,nodeNum=1;
node *root,*ptr;
queue<node*> Queue;
root=new node;
root->arrTo(a);
for(i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
{
if(a[i][j]==0)
{
root->x=i;
root->y=j;
}
}
}
ptr=root;
Queue.push(ptr);
node* p=NULL;
while(!Queue.empty())
{
ptr=Queue.front();
Queue.pop();
nodeNum--;
if(ptr->IsGoal())
{
ptr->Show();
cout<<endl;
while(ptr->parent!=NULL){
ptr->parent->Show();
ptr=ptr->parent;
steps++;
cout<<endl;
}
cout<<"Steps:"<<steps<<endl;
root->Delete(root);
return 0;
}else
{
if((ptr->y+1)<SIZE)
{
if(ptr->parent==NULL)
{
p=new node;
if(p==NULL)
{
root->Delete(root);
cout<<"空间不足，程序终止运行。\n";
return 0;
}
p->x=ptr->x;
p->y=ptr->y+1;
p->arrTo(ptr->a);
p->a[ptr->x][ptr->y]=p->a[p->x][p->y];
p->a[p->x][p->y]=0;
ptr->right=p;
p->parent=ptr;
Queue.push(p);
nodeNum++;
}
else
{
if((ptr->x)!=(ptr->parent->x) || ((ptr->y)+1)!=(ptr->parent->y))
{
p=new node;
if(p==NULL)
{
root->Delete(root);
cout<<"空间不足，程序终止运行。\n";
return 0;
}
p->x=ptr->x;
p->y=ptr->y+1;
p->arrTo(ptr->a);
p->a[ptr->x][ptr->y]=p->a[p->x][p->y];
p->a[p->x][p->y]=0;
ptr->right=p;
p->parent=ptr;
Queue.push(p);
nodeNum++;
}
}
}
if((ptr->x-1)>=0)
{
if(ptr->parent==NULL){
p=new node;
if(p==NULL)
{
root->Delete(root);
cout<<"空间不足，程序终止运行。\n";
return 0;
}
p->x=ptr->x-1;
p->y=ptr->y;
p->arrTo(ptr->a);
p->a[ptr->x][ptr->y]=p->a[p->x][p->y];
p->a[p->x][p->y]=0;
ptr->up=p;
p->parent=ptr;
Queue.push(p);
nodeNum++;
}else
if(((ptr->x)-1)!=(ptr->parent->x) || (ptr->y)!=(ptr->parent->y))
{
p=new node;
if(p==NULL)
{
root->Delete(root);
cout<<"空间不足，程序终止运行。\n";
return 0;
}
p->x=ptr->x-1;
p->y=ptr->y;
p->arrTo(ptr->a);
p->a[ptr->x][ptr->y]=p->a[p->x][p->y];
p->a[p->x][p->y]=0;
ptr->up=p;
p->parent=ptr;
Queue.push(p);
nodeNum++;
}
}
if((ptr->x+1)<SIZE)
{
if(ptr->parent==NULL){
p=new node;
if(p==NULL)
{
root->Delete(root);
cout<<"空间不足，程序终止运行。\n";
return 0;
}
p->x=ptr->x+1;
p->y=ptr->y;
p->arrTo(ptr->a);
p->a[ptr->x][ptr->y]=p->a[p->x][p->y];
p->a[p->x][p->y]=0;
ptr->down=p;
p->parent=ptr;
Queue.push(p);
nodeNum++;
}else
{
if(((ptr->x)+1)!=(ptr->parent->x) || (ptr->y)!=(ptr->parent->y))
{
p=new node;
if(p==NULL)
{
root->Delete(root);
cout<<"空间不足，程序终止运行。\n";
return 0;
}
p->x=ptr->x+1;
p->y=ptr->y;
p->arrTo(ptr->a);
p->a[ptr->x][ptr->y]=p->a[p->x][p->y];
p->a[p->x][p->y]=0;
ptr->down=p;
p->parent=ptr;
Queue.push(p);
nodeNum++;
}
}
}
if((ptr->y-1)>=0)
{
if(ptr->parent==NULL)
{
p=new node;
if(p==NULL)
{
root->Delete(root);
cout<<"空间不足，程序终止运行。\n";
return 0;
}
p->x=ptr->x;
p->y=ptr->y-1;
p->arrTo(ptr->a);
p->a[ptr->x][ptr->y]=p->a[p->x][p->y];
p->a[p->x][p->y]=0;
ptr->left=p;
p->parent=ptr;
Queue.push(p);
nodeNum++;
}else
{
if((ptr->x)!=(ptr->parent->x) || ((ptr->y)-1)!=(ptr->parent->y))
{
p=new node;
if(p==NULL)
{
root->Delete(root);
cout<<"空间不足，程序终止运行。\n";
return 0;
}
p->x=ptr->x;
p->y=ptr->y-1;
p->arrTo(ptr->a);
p->a[ptr->x][ptr->y]=p->a[p->x][p->y];
p->a[p->x][p->y]=0;
ptr->left=p;
p->parent=ptr;
Queue.push(p);
nodeNum++;
}
}
}
}
if(nodeNum>10000000)
{
cout<<"小弟无能，找不到答案！！！\n";
root->Delete(root);
return 0;
}
}
return 0;
}
