TIOJ 1569 8 Puzzle - the Hyper version [IDA*]

poao899    1569    Accepted    -8K    244MS    G++    1.08K    2009-12-16 16:15:50                                     .




第二題IDA*(咦


H():一樣漢米頓距離不過注意有穿透所以行列上線都是1 所以每個數字的答案都只可能是012中的一個


//**************************

#include<stdio.h>
/*
0 1 2
3 4 5
6 7 8
*/
int dir[9][4]={
	1,3,10,10,
	0,2,4,7,
	1,5,10,10,
	0,4,6,5,
	1,3,5,7,
	2,4,8,3,
	3,7,10,10,
	4,6,8,1,
	5,7,10,10,
};
inline void sw(int &a,int &b){
	a^=b^=a^=b;
}
inline int abs(int a){
	return a>0?a:-a;
}
int puz[10],ans[10],dmax,z;
int h(){
	int sum=0;
	for(int i=0;i<9;i++){
		if(puz[i]){
			//printf("puz%d ans%d\n",puz[i],ans[puz[i]]);
			sum+=((puz[i]-1)%3!=i%3)+((puz[i]-1)/3!=i/3);
		}
	}
	return sum;
}
int dfsid(int depth,int pre){
	int hv=h(),rp;
	if(depth+hv>dmax)return -1;
	if(hv==0)return depth;
	for(int i=0;i<9;i++){
		if(puz[i]==0){
			//printf("puz %d\n",i);
			for(int j=0;j<4;j++){
				if(dir[i][j]!=10 && dir[i][j]!=pre){
					sw(puz[dir[i][j]],puz[i]);
					//if(h()<hv){
					rp=dfsid(depth+1,i);
					//}else rp=-1;
					sw(puz[dir[i][j]],puz[i]);
					if(~rp)return rp;
				}
			}
			return -1;
		}
	}
}
main(){
	for(int i=0;i<9;i++)scanf("%d",puz+i);
	int way;
	for(dmax=0;;dmax++){
		//printf("%d\n",dmax);
		way=dfsid(0,-1);
		if(~way)break;
	}
	printf("%d\n",way);
}