HDU 2234 无题I IDA*搜索

转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

继续IDA*。

有16种变化，但是是有规律的，不需要一一列出。每次变化改变4个位置，估价函数是，最少的可能不满足要求的个数+3/4和上题有点像。

跑进了2s内，还不错，不知道31ms是怎么写的。

其中IDA*搜索的时候还是用到了父节点优化，比如上一步是第一列向上，那么下一步不会做第一列向下。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#include<vector>#include<cmath>#include<map>#include<string>#define inf 1<<30#define eps 1e-7#define LD long double#define LL long long#define maxn 1005using namespace std;int a[4][4];int depth;bool flag;void change(int b[4][4],int k){if(k<8){if(k&1){int tmp=b[0][k/2];for(int i=1;i<4;i++)b[i-1][k/2]=b[i][k/2];b[3][k/2]=tmp;}else{int tmp=b[3][k/2];for(int i=3;i>0;i--)b[i][k/2]=b[i-1][k/2];b[0][k/2]=tmp;}}else{if(k&1){int tmp=b[(k-8)/2][0];for(int i=1;i<4;i++)b[(k-8)/2][i-1]=b[(k-8)/2][i];b[(k-8)/2][3]=tmp;}else{int tmp=b[(k-8)/2][3];for(int i=3;i>0;i--)b[(k-8)/2][i]=b[(k-8)/2][i-1];b[(k-8)/2][0]=tmp;}}}int get_h(int b[4][4]){int ans=inf,tmp=0;for(int i=0;i<4;i++){bool flag[5];int cnt=4;memset(flag,false,sizeof(flag));for(int j=0;j<4;j++)if(!flag[b[i][j]]){cnt--;flag[b[i][j]]=true;}tmp+=3-cnt;}ans=min(tmp,ans);tmp=0;for(int j=0;j<4;j++){bool flag[5];int cnt=4;memset(flag,false,sizeof(flag));for(int i=0;i<4;i++)if(!flag[b[i][j]]){cnt--;flag[b[i][j]]=true;}tmp+=3-cnt;}ans=min(tmp,ans);return (ans+3)/4;}void IDAstar(int b[4][4],int tmp_depth,int father){if(flag)return;if(get_h(b)>tmp_depth)return;if(tmp_depth==0){flag=true;return;}for(int i=0;i<16;i++){if(father!=-1&&father/2==i/2&&(father%2)^(i%2))continue;int tmp[4][4];for(int i=0;i<4;i++)for(int j=0;j<4;j++)tmp[i][j]=b[i][j];change(tmp,i);IDAstar(tmp,tmp_depth-1,i);}}int main(){int t;scanf("%d",&t);while(t--){for(int i=0;i<4;i++)for(int j=0;j<4;j++)scanf("%d",&a[i][j]);flag=false;for(depth=0;depth<=5;depth++){IDAstar(a,depth,-1);if(flag){printf("%d\n",depth);break;}}if(!flag)printf("-1\n");}return 0;}