【文章內(nèi)容簡(jiǎn)介】 B[N][N]={ {1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,0} }。int n=0。//記錄步數(shù)int x,y。bool check(){ //判斷是否有路徑，根據(jù)初始態(tài)和目標(biāo)態(tài)的秩序，若不同為奇數(shù)或同為偶數(shù)，則無(wú)路徑 int temp=A[x][y]。 int i,j,sum2 = 0,sum1 = 0。 int a[N*N],b[N*N]。 for(i=0。iN。i++){ for(j=0。jN。j++){ a[i*N+j]=A[i][j]。 } } for(i=0。iN。i++){ for(j=0。jN。j++){ b[i*N+j]=B[i][j]。 } } for(i=0。iN*N1。i++){ for(j=i+1。jN*N。j++){ if(a[i]!=tempamp。amp。a[j]!=tempamp。amp。a[i]a[j]) sum1++。 } } for(i=0。iN*N1。i++){ for(j=i+1。jN*N。j++){ if(b[i]!=tempamp。amp。b[j]!=tempamp。amp。b[i]b[j]) sum2++。 } } if((sum1%2==0amp。amp。sum2%2==1)||(sum1%2==1amp。amp。sum2%2==0)){ return false。 } return true。}bool begin_opint(){ int i,j。 for(i=0。iN。i++){ for(j=0。jN。j++){ if(A[i][j]==0){ x=i。y=j。 return true。} } } return false。}bool pare(int a[N][N]){ int i,j。 for(i=0。iN。i++){ for(j=0。jN。j++){ if(a[i][j]!=B[i][j]) return false。 } } return true。}bool moveleft(int a[N][N],QueuePtr *b,int x,int y){ int k,i,j。 if(y==0) return false。 for(i=0。iN。i++){ for(j=0。jN。j++) (*b)data[i][j]=a[i][j]。 } k=(*b)data[x][y]。 (*b)data[x][y]=(*b)data[x][y1]。 (*b)data[x][y1]=k。 (*b)x=x。 (*b)y=y1。 return true。}bool moveup(int a[N][N],QueuePtr *b,int x,int y){ int k,i,j。 if(x==0) return false。 for(i=0。iN。i++){ for(j=0。jN。j++) (*b)data[i][j]=a[i][j]。 } k=(*b)data[x][y]。 (*b)data[x][y]=(*b)data[x1][y]。 (*b)data[x1][y]=k。 (*b)x=x1。 (*b)y=y。 return true。}bool movedown(int a[N][N],QueuePtr *b,int x,int y){ int k,i,j。 if(x==N1)return false。 for(i=0。iN。i++){ for(j=0。jN。j++) (*b)data[i][j]=a[i][j]。 } k=(*b)data[x][y]。 (*b)data[x][y]=(*b)data[x+1][y]。 (*b)data[x+1][y]=k。 (*b)x=x+1。 (*b)y=y。 return true。}bool moveright(int a[N][N],QueuePtr *b,int x,int y){ int k,i,j。 if(y==N1) return false。 for(i=0。iN。i++){ for(j=0。jN。j++) (*b)data[i][j]=a[i][j]。 } k=(*b)data[x][y]。 (*b)data[x][y]=(*b)data[x][y+1]。 (*b)data[x][y+1]=k。 (*b)x=x。 (*b)y=y+1。 return true。}bool copy(QueuePtr *a){ int i,j。 for(i=0。iN。i++){ for(j=0。jN。j++) (*a)data[i][j]=A[i][j]。 } return true。}void output(int a[N][N]){ int i,j。 for(i=0。iN。i++){ for(j=0。jN。j++){ printf( %d,a[i][j])。 }printf(\n)。 }printf(\n)。}void main(){ QueuePtr closed,p,q。 LinkQueue open。 /*if(!check()){ printf(no answer!!\n)。 //no answer exit(0)。 }*/ if(!begin_opint()){ printf(no 0 opint!!\n)。 //確定0點(diǎn) exit(0)。 } =(QueuePtr)malloc(sizeof(QNode))。//頭結(jié)點(diǎn) next=NULL。 closed=(QueuePtr)malloc(sizeof(QNode))。//頭結(jié)點(diǎn) closednext=NULL。 p=(QueuePtr)malloc(sizeof(QNode))。//S0進(jìn)open表 copy(amp。p)。 px=x。 py=y。 pancent=5。 pdeep=0。 //s0的深度為0 pnext=next。 next=p。 while(next!=NULL){ q=next。 //open進(jìn)closed next=qnext。 //移除open表頭結(jié)點(diǎn) qnext=closednext。 //插入closed表的表頭 closednext=q。 if(qdeepDEEP){ n++。 output(qdata)。 if(pare(qdata)){ printf(ok!\n)。 printf(steps is %d\n,n)。 exit(0)。 } //將后繼結(jié)點(diǎn)放入open表中 switch(closednextancent){ //左上右下 1234 case 1: p=(QueuePtr)malloc(sizeof(QNode))。//祖先結(jié)點(diǎn)從右來(lái) if(moveleft(closednextdata,amp。p,closednextx,closednexty)){ pancent=1。 pdeep=closednextdeep+1。 pnext=next。 next=p。 }else free(p)。 p=(QueuePtr)malloc(sizeof(QNode))。// if(moveup(closednextdata,amp。p,closednextx,closednexty)){ pancent=2。 pdeep=closednextdeep+1。 pnext=next。 next=p。 }else free(p)。 p=(QueuePtr)malloc(sizeof(QNode))。// if(movedown(closednextdata,amp。p,closednextx,closednexty)){ pancent=4。 pdeep=closednextdeep+1。 pnext=next。 next=p。 }else free(p)。 break。 case 2:p=(QueuePtr)malloc(sizeof(QNode))。//祖先結(jié)點(diǎn)從下來(lái) if(moveleft(closednextdata,amp。p,closednextx,closednexty)){ pancent=1。 pdeep=closednextdeep+1。 pnext=next。 next=p。 }else free(p)。 p=(QueuePtr)malloc(sizeof(QNode))。// if(moveup(closednextdata,amp。p,closednextx,closednexty)){ pancent=2。 pdeep=closednextdeep+1。 pnext=next。 next=p。 }else free(p)。 p=(QueuePtr)malloc(sizeof(QNode))。// if(moveright(closednextdata,amp。p,closednextx,closednexty)){ pancent=3。 pdeep=closednextdeep+1。 pnext=next。 next=p。 }else free(p)。 break。 case 3:p=(QueuePtr)malloc(sizeof(QNode))。//祖先結(jié)點(diǎn)從左來(lái) if(moveup(closednextdata,amp。p,closednextx,closednexty)){ pancent=2。 pdeep=closednextdeep+1。 pnext=next。 next=p。 }else free(p)。 p=(QueuePtr)malloc(sizeof(QNode))。// if(moveright(closednextdata,amp。p,closednextx,closednexty)){ pancent=3。 pdeep=closednextdeep+1。 pnext=next。 next=p。 }else free(p)。 p=(QueuePtr)malloc(sizeof(QNode))。// if(movedown(closednextdata,amp。p,closednextx,closednexty)){ pancent=4。 pdeep=closednextdeep+1。 pnext=next。 next=p。 }else free(p)。 break。 case 4: p=(QueuePtr)malloc(sizeof(QNode))。//祖先結(jié)點(diǎn)從上邊來(lái) if(moveleft(closednextdata,amp。p,closednextx,closednexty)){ pancent=1。 pdeep=closednextdeep+1。 pnext=next。 next=p。 }else free(p)。 p=(QueuePtr)malloc(sizeof(QNode))。// if(moveright(closednextdata,amp。p,closednextx,closednext