#include<iostream>
#include<stdio.h>
#include<math.h>
#define N 3
#define M 100000

using namespace std;


class jgnode{
public:
	int value[N][N];                 //記錄九宮各位置的值
	int num[2];                      //記錄0的位置
	int h;
	jgnode *pre;                  //指向父輩節點的指針
	jgnode *next;
	jgnode():pre(NULL)            //默認構造函數
	{}

	jgnode(const int v[N][N],jgnode *p=NULL){//構造函數初始化
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				value[i][j]=v[i][j];
		pre=p;
	}
	jgnode(const int v[N][N],jgnode *p=NULL,int n[2]=0){
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				value[i][j]=v[i][j];
		pre=p;
		num[0]=n[0];
		num[1]=n[1];
		h=0;
		next=NULL;
	}

	void setp(jgnode *p){            //設置父輩節點的指針
		pre=p;
	}
	void setv(int *v){               //設置記錄九宮各位置的值
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				value[i][j]=v[i*3+j];
	}
	void setn(int n[2]){num[0]=n[0];num[1]=n[1];}          //設置0的位置
	void print(){                     //輸出九宮
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++)
				cout<<value[i][j]<<"  ";
			cout<<endl;}
		cout<<endl;
	}
	int isequal(int v[N][N]){
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				if(value[i][j]!=v[i][j])
					return -1;
		return 0;
	}

};

void findzero(int tv[N][N],int tn[2]);
int expand(jgnode *h,jgnode *t,jgnode *g,int gp[9][2]);
int isgnode(jgnode *t,jgnode *g,int tv[N][N]);
int printnode(jgnode *g);
void evalue(jgnode *t,int tv[N][N]);
int expnode(jgnode *h,jgnode *t,int tv[N][N],int tn[2],int gp[9][2]);
int hfunct(int tv[N][N],int gp[9][2]);
void enopen(jgnode *h,jgnode *temp);

int main(){
	int vs[N][N]={1,2,3,4,0,5,6,7,8},vg[N][N]={0,1,2,3,4,5,6,7,8},vt[N][N],tnum[2]={0,0};
/*	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			vg[i][j]=vs[2-i][2-j];*/
	int ecount=1,ocount=0,ccount=0,j=0,temp=0,counter=0;
	char cho='n';
do{
	//ecount記錄open表末端，ocount記錄open表始端，ccount記錄closed表末端
	jgnode *closed[M]={NULL};
	jgnode *snode=NULL,*gnode=NULL,*tnode=NULL,*head=NULL;
	//snode為開時節點，gnode為目標節點，tnode為寄存節點
	cout<<"輸入開始節點（如1,2,3,4,0,5,6,7,8）："<<endl;
	for(int m=0;m<N;m++)
		for(int n=0;n<N;n++)
			cin>>vs[m][n];//scanf("%d",&vs[m][n]);
	int gp[9][2]={{0,0},{0,1},{0,2},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2}};
	findzero(vs,tnum);
	snode=new jgnode(vs,NULL,tnum);
	snode->h=hfunct(vs,gp);
	cout<<snode->h<<endl;
	//cout<<"出入目標節點（如3、1、2、4、0、5、6、7、8）："<<endl;
	//for(m=0;m<N;m++)
	//	for(int n=0;n<N;n++)
	//		cin>>vg[m][n];//scanf("%d",&vg[m][n]);
	gnode=new jgnode(vg,NULL,tnum);
	cout<<"開始節點："<<endl;
	snode->print();
	cout<<"目標節點："<<endl;
	gnode->print();
	head=snode;
	cout<<"start:"<<endl;
	if(snode->isequal(vg)==0){
		cout<<"find with th snode."<<endl;
		return 0;
	}
	ecount=expand(head,snode,gnode,gp);
	if(ecount==-1)
		return 0;
	while(j++<M){
		if(head->next==NULL)
			break;
		tnode=head->next;
		head->next=tnode->next;
		evalue(tnode,vt);
		while(closed[counter]!=NULL){
			if(closed[counter++]->isequal(vt)==0){
				temp=1;break;}
		}
		if(temp==0){
		closed[ccount++]=tnode;
		ecount=expand(head,tnode,gnode,gp);
		if(ecount==-1)
			break;
		}
		temp=0;counter=0;
	}
	cout<<"擴展次數為:  "<<j<<endl;
/*	while(head!=NULL){
		cout<<head->h<<endl;
		head->print();
		head=head->next;
	}
	int ccc=0;
	while(closed[ccc]!=NULL){
		cout<<closed[ccc]->h<<endl;
		closed[ccc++]->print();
	}*/
	j=0;
	cout<<"是否繼續下一次搜索（y or n）:"<<endl;
	cin>>cho;
	}while((cho=='y')||(cho=='Y'));
	return 0;
}

int printnode(jgnode *g,int c){
	int cc=c;
	if((g->pre)!=NULL)
		cc=printnode(g->pre,c+1);
	g->print();
	return cc;
}
int isgnode(jgnode *t,jgnode *g,int tv[N][N]){
	int count=0;
	if(g->isequal(tv)==0){
		g->pre=t;
		cout<<"find the goal node!!"<<endl;
		cout<<"搜索路徑如下："<<endl;
		count=printnode(g,count);
		cout<<"路徑長度："<<count<<endl;
		return -1;
	}
	return 0;
}
int expnode(jgnode *h,jgnode *t,int tv[N][N],int tn[2],int gp[9][2]){
	jgnode *temp;
	if((t->pre)!=NULL){
		if(((t->pre)->isequal(tv))!=0){
			temp=new jgnode(tv,t,tn);
			temp->pre=t;
			temp->h=hfunct(tv,gp);//yaogai
			//cout<<temp->h<<endl;
			//temp->print();
			enopen(h,temp);
			return 1;
		}
		else return 0;
	}
	else{
		temp=new jgnode(tv,t,tn);
		temp->pre=t;
		temp->h=hfunct(tv,gp);//yaogai
		//cout<<temp->h<<endl;
		//temp->print();
		enopen(h,temp);
		return 1;
	}
}
//擴展當前節點，并判斷是否為目標
int expand(jgnode *h,jgnode *t,jgnode *g,int gp[9][2]){
	int td=0,ti,tj,tv[N][N],tn[2],ct=0,flag=0;
	ti=t->num[0];tj=t->num[1];
    if((ti-1)>=0){
		evalue(t,tv);
		tn[0]=ti-1;tn[1]=tj;
		td=tv[ti-1][tj];tv[ti-1][tj]=tv[ti][tj];tv[ti][tj]=td;
		if(isgnode(t,g,tv)==-1)
			return -1;
		expnode(h,t,tv,tn,gp);
	}
    if((tj+1)<=2){
		evalue(t,tv);
		tn[0]=ti;tn[1]=tj+1;
		td=tv[ti][tj+1];tv[ti][tj+1]=tv[ti][tj];tv[ti][tj]=td;
		if(isgnode(t,g,tv)==-1)
			return -1;
		expnode(h,t,tv,tn,gp);
	}
    if((ti+1)<=2){
		evalue(t,tv);
		tn[0]=ti+1;tn[1]=tj;
		td=tv[ti+1][tj];tv[ti+1][tj]=tv[ti][tj];tv[ti][tj]=td;
		if(isgnode(t,g,tv)==-1)
			return -1;
		expnode(h,t,tv,tn,gp);
	}
    if((tj-1)>=0){
		evalue(t,tv);
		tn[0]=ti;tn[1]=tj-1;
		td=tv[ti][tj-1];tv[ti][tj-1]=tv[ti][tj];tv[ti][tj]=td;
		if(isgnode(t,g,tv)==-1)
			return -1;
		expnode(h,t,tv,tn,gp);
	}
	return 0;
}
void evalue(jgnode *t,int tv[N][N]){
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			tv[i][j]=t->value[i][j];
}

int hfunct(int tv[N][N],int gp[9][2]){
	int p=0,s=0;
	int pp[9][2]={{0,1},{0,2},{1,2},{0,0},{1,1},{2,2},{1,0},{2,0},{2,1}};
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			p+=abs(i-gp[(tv[i][j])][0])+abs(j-gp[(tv[i][j])][1]);
			if((i!=1)||(j!=1)){
				if(tv[(pp[i*3+j][0])][(pp[i*3+j][1])]!=((pp[i*3+j][0])*3+pp[i*3+j][1]))
					s+=2;
			}
		}
	}
	if(tv[1][1]!=0)
		s+=1;
	return p+3*s;
}
void enopen(jgnode *h,jgnode *temp){
	jgnode *pt=h->next,*q=h;
	while(pt!=NULL){
		if(temp->h<pt->h){
			temp->next=pt;
			q->next=temp;
			break;
		}
		q=pt;
		pt=pt->next;
	}
	if((pt==NULL)&&(temp->next==NULL))
		q->next=temp;
	//cout<<temp->h<<endl;
	//temp->print();
}

void findzero(int tv[N][N],int tn[2]){
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++){
			if(tv[i][j]==0){tn[0]=i;tn[1]=j;}
		}
}