#include<iostream>
#include<stdio.h>
#define N 3              //九宮二維數組大小
#define M 100000         //closed表的大小，可進行設置

using namespace std;


class jgnode{
public:
	int value[N][N];                 //記錄九宮各位置的值
	int num[2];                      //記錄0的位置
	jgnode *pre;                  //指向父輩節點的指針
	jgnode *next;                 //open表中連接后面節點的指針
	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];
		next=NULL;
	}

	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 isgnode(jgnode *t,jgnode *g,int tv[N][N]);
int printnode(jgnode *g,int c);
void evalue(jgnode *t,int tv[N][N]);
int expnode(jgnode *h,jgnode *t,int tv[N][N],int tn[2]);

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];*/
	char cho='n';
do{	int ecount=1,ocount=0,ccount=0,j=0,temp=0,counter=0;
	//ecount記錄open表末端，ocount記錄open表始端，ccount記錄closed表末端
	jgnode *head=NULL,*end=NULL,*closed[M]={NULL};
	jgnode *snode=NULL,*gnode=NULL,*tnode=NULL,*tt=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];
	findzero(vs,tnum);
	cout<<tnum[0]<<tnum[1]<<endl;
	snode=new jgnode(vs,NULL,tnum);
/*	cout<<"出入目標節點（如0,1,2,3,4,5,6,7,8）："<<endl;
	for(m=0;m<N;m++)
		for(int n=0;n<N;n++)
			cin>>vg[m][n];*/
	gnode=new jgnode(vg,NULL,tnum);
	cout<<"開始節點："<<endl;
	snode->print();
	cout<<"目標節點："<<endl;
	gnode->print();
	head=snode;end=head;tt=head;
	cout<<"start:"<<endl;
	if(snode->isequal(vg)==0){
		cout<<"find with th snode."<<endl;
		return 0;
	}
	ecount=expand(head,snode,gnode);
//	while(tt!=NULL){
//		tt->print();
//		tt=tt->next;
//	}
	tt=head;
	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);
		if(ecount==-1)
			break;
		}
		temp=0;counter=0;
/*		while(tt!=NULL){
		tt->print();
		tt=tt->next;
		}
	    tt=head;*/
	}
	cout<<"擴展次數為:  "<<j<<endl;
/*	int ccc=0;
	while(closed[ccc]!=NULL){
		closed[ccc++]->print();
	}
	while(head!=NULL){
		head->print();
		head=head->next;
	}*/
	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]){
	jgnode *temp,*p=h;
	if((t->pre)!=NULL){
		if(((t->pre)->isequal(tv))!=0){
			temp=new jgnode(tv,t,tn);
			temp->pre=t;
			while(p->next!=NULL)
				p=p->next;
			p->next=temp;
			temp=NULL;
			return 1;
		}
		else return 0;
	}
	else{
		temp=new jgnode(tv,t,tn);
		temp->pre=t;
		while(p->next!=NULL)
			p=p->next;
		p->next=temp;
		temp=NULL;
		return 1;
	}
}
//擴展當前節點，并判斷是否為目標
int expand(jgnode *h,jgnode *t,jgnode *g){
	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);
	}
    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);
	}
    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);
	}
    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);
	}
	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];
}

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;}
		}
}