HDU1043&&POJ1077
题意：将八数码还原成原位
做法（参照各种神牛牪犇）
1.判断是否有解，原位时八数码的逆序对一定是0，细心的人就会发现每次移动的逆序对是偶数次变换的，所以只用判断初始情况的逆序对是否为偶数即可
2.强力剪枝：1.用H最优估计剩余步数（曼哈顿距离） 2.限制深度deep，每次加一 3.判断与上一步是否反向
3.IDA* 每次限制层数加一，逐层搜索。
注意：在算H的时候直接将原位设为设为标准位置即可。
#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; const int goal[10][2]={{2,2},{0,0},{0,1}, {0,2},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2}}; const char op[4] = {'r', 'd', 'u', 'l'}; const int dir[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; char path[100]; int abs(int x) { return x<0? -x:x; } int inv(int *a) { int ans=0; for(int i=0;i<9;++i) { if(a[i]==0) continue; for(int j=i+1;j<9;++j) { if(a[i]>a[j]&&a[j]) ans++; } } return ans; } int geth(int *num) { int cost=0; for(int i=0;i<9;++i) { cost+= abs(goal[num[i]][0]-i/3) + abs(goal[num[i]][1]-i%3); } return cost; } bool dfs(int *a,int x,int y,int len, int pre,int deep) { for(int i=0;i<4;++i) { int xx=x+dir[i][0],yy=y+dir[i][1]; if(pre+i==3 || xx<0|| xx>2|| yy<0|| yy>2) continue; a[3*x+y]=a[3*xx+yy]; a[3*xx+yy]=0; int h=geth(a); if(h==0) { path[len] = op[i]; path[len+1]= '\0'; return 1; } if(h+len<=deep) { path[len]=op[i]; if(dfs(a,xx,yy,len+1,i,deep)) return 1; } a[3*xx+yy]=a[3*x+y]; a[3*x+y]=0; } return 0; } int main() { char str[10]; while(scanf(" %c",&str[0])!=EOF) { for(int i=1;i<9;++i) scanf(" %c",&str[i]); int a[10],sx,sy; for(int i=0;i<9;++i) { if(str[i]=='x') { sx=i/3; sy=i%3; a[i]=0; } else a[i]=str[i]-'0'; } if(inv(a)%2==1) { printf("unsolvable\n"); } else { int ans=geth(a); if(ans==0) printf("\n"); else { int deep=0; while(++deep) { if(dfs(a,sx,sy,0,-1,deep)) break; } puts(path); } } } return 0; }
HDU 3567
题意描述：经典八数码问题，给定起始状态和目标状态，经过d、l、r、u移动，求解如何移动能使起始状态到达目标状态？ 1、移动的次数尽可能少 2、如果移动次数相同，求解移动序列的最小字典序？
解题思路：典型的IDA*题目 1.估值函数：从当前状态移动到目标状态所需的最小步数（我们可以通过曼哈顿距离进行估值），用于剪枝 2.迭代：此处我们不再使深度每次加1（会TLE），而是在搜索过程当中，记录大于len（len表示此次搜索的限制深度）的所有值中的最小值，作为下次迭代的限制深度。
3.判重:使用康拓展开，将目标状态存为标准情况，同时用vis来判重。
4.计算h的时候也是以目标状态为标准。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> using namespace std; const int maxn=4e5+5; int vis[maxn]; int st[9], goal[9]; const int dir[][2] = {1,0, 0,-1, 0,1, -1,0}; const char op[] = {'d','l','r','u'}; int fact[9], loc[9]; int getkt(int *a) { int code = 0; for(int i = 0; i < 9; ++i) { int cnt = 0; for(int j = i + 1; j < 9; ++j) if(a[j] < a[i]) cnt++; code += fact[8 - i] * cnt; } return code; } int geth(int *a) { int cnt = 0; for(int i = 0; i < 9; ++i) { if(a[i] == 0 || i == loc[a[i]]) continue; int x=i/3, y=i%3; int n=loc[a[i]]; int px=n/3,py=n%3; cnt+=abs(x - px)+abs(y - py); } return cnt; } char ans[50]; int deep, nextdeep; int dfs(int*a,int step, int pos) { int h = geth(a); if(h == 0) { printf("%d\n", step); ans[step] = '\0'; printf("%s", ans); return 1; } if(step + h > deep) { nextdeep = min(nextdeep, step + h); return 0; } int x=pos/3, y =pos%3; for(int i = 0; i < 4; ++i) { int xx=x+dir[i][0], yy=y+dir[i][1]; if(xx<0||yy<0||xx>2||yy>2) continue; swap(a[pos], a[xx*3+yy]); int code = getkt(a); if(vis[code]) { swap(a[pos], a[xx*3+yy]); continue; } vis[code]=1; ans[step]=op[i]; if(dfs(a,step+1, xx*3+yy)) return 1; vis[code] = 0; swap(a[pos], a[xx*3+yy]); } return 0; } int main() { fact[0] = 1; for(int i = 1; i < 9; ++i) fact[i] = fact[i - 1] * i; char str[50]; int T, kase = 1; scanf("%d", &T); while(T--) { int pos; scanf("%s",str); for(int i = 0; i < 9; ++i) { if(str[i] == 'X') { pos = i; st[i] = 0; } else st[i] = str[i] - '0'; } scanf("%s",str); for(int i = 0; i < 9; ++i) { if(str[i] == 'X') goal[i] = 0; else goal[i] = str[i] - '0'; } for(int i = 0; i < 9; ++i) loc[goal[i]] = i; printf("Case %d: ", kase++); int code = getkt(st); for(deep = geth(st);;) { nextdeep=1<<30; memset(vis,0,sizeof(vis)); vis[code]=1; if(dfs(st,0, pos)) break; deep = nextdeep; } printf("\n"); } return 0; }
