IDA*就是基于迭代深搜上的A*算法，最主要的就是在迭代深搜的过程中加了一个估价函数，关键还是这个估价函数的构造，ORZ，少了这个估价函数，对于这题目的话，直接TLE的说。
这题目的估价函数是这样的，根据目前的地图简单的判断一下至少还要转多少次吧。
这个估价函数“每次移动改变四个点的位置，即h()=(最少可能的横向或纵向不在位置上的点的个数+3)/4 )”，是参照大牛的。至于这么判断的，就要结合代码好好理解了……
至于迭代加深，在之前的题目已经接触过了
#include<iostream> #include<algorithm> using namespace std; int map[5][5],step; inline int check() { bool vis[5]; int cnt,temp=0,minn=20; for(int i=0;i<4;i++) { cnt=4; memset(vis,0,sizeof(vis)); for(int j=0;j<4;j++) { if(vis[map[i][j]])continue; vis[map[i][j]]=true; cnt--; } temp+=3-cnt;//通俗一点的说，3-cnt表示的是这一行或列有多少个数字是不应该出现的 } if(temp<minn) minn=temp; temp=0; for(int j=0;j<4;j++) { cnt=4; memset(vis,0,sizeof(vis)); for(int i=0;i<4;i++) { if(vis[map[i][j]])continue; vis[map[i][j]]=true; cnt--; } temp+=3-cnt; } if(temp<minn) minn=temp; return minn;//最后的minn保存的是按行或列来转，最少有多少个位置是错的 } void TurnL(int x) { int t=map[x][0]; for(int i=1;i<4;i++) map[x][i-1]=map[x][i]; map[x][3]=t; } void TurnR(int x) { int t=map[x][3]; for(int i=2;i>=0;i--) map[x][i+1]=map[x][i]; map[x][0]=t; } void TurnU(int x) { int t=map[0][x]; for(int i=1;i<4;i++) map[i-1][x]=map[i][x]; map[3][x]=t; } void TurnD(int x) { int t=map[3][x]; for(int i=2;i>=0;i--) map[i+1][x]=map[i][x]; map[0][x]=t; } bool dfs(int cnt) { int temp=check(); if(cnt==step && temp==0) return true; if(cnt+(temp+3)/4>step)//除以4 是最理想化的情况，转一次使四个数字回到正确的位置，+3就比较好理解了 return false; for(int i=0;i<4;i++) { TurnL(i); if(dfs(cnt+1)) return true; TurnR(i); TurnR(i); if(dfs(cnt+1)) return true; TurnL(i); TurnU(i); if(dfs(cnt+1)) return true; TurnD(i); TurnD(i); if(dfs(cnt+1)) return true; TurnU(i); } return false; } int main() { int cas; scanf("%d",&cas); while(cas--) { for(int i=0;i<4;i++) for(int j=0;j<4;j++) scanf("%d",&map[i][j]); if(!check()) { puts("0"); continue; } step=1; while(true) { if(step>5)break; if(dfs(0)) break; step++; } if(step>5)puts("-1"); else printf("%d\n",step); } return 0; }
转载于:https://www.cnblogs.com/nanke/archive/2011/12/08/2281153.html
相关资源：数据结构—成绩单生成器