Eight HDU - 1043（八数码， 康托展开+逆向BFS打表）

Eight

题目链接： HDU - 1043
题意：

                   <1> 图                                              <2> 图

要求由<1>图变到<2>图， 求出路径；

每块格子只能和上下左右四个方向的格子交换，

网上有用A*写的， 不需要那么麻烦， 逆向BFS加上康托展开剪枝就可以；（C++过的， G++超内存了~~~， 不知所以的茫然）；

什么是康托展开？戳这里

说一下为什么要逆向求；

由于最终状态都是12345678x， 所以由最终状态开始退回去可以到达的状态一定可以到达最终状态， 反之一定到不了最终状态；

这样， 在逆向求的时候直接对每个状态到最终状态的解记录；

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int maxn=362880;
int fact[]={1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int canto_ex(int a[]){//康托展开；int sum=0;for(int i=0; i<9; i++){int tmp=0;for(int j=i+1; j<9; j++)if(a[j]<a[i]) tmp++;sum+=tmp*fact[8-i];}return sum;
}
void re_canto_ex(int sum, int a[]){//康托逆展开；int k=sum, x;int vis[10];for(int i=1; i<10; i++) vis[i]=0;for(int i=0; i<9; i++){x=k/fact[8-i];k=k%fact[8-i];for(int j=1; j<=9; j++){if(vis[j]) continue;if(x==0) a[i]=j, vis[j]=1;x--;}}return;
}
struct node{int canto_val, pre, pos;
}que[maxn];
string path[maxn];//存每个状态对应的路径， 状态用康托展开求；
int vis[maxn];
int dir[4][2]={1, 0, -1, 0, 0, -1, 0, 1};//四个方向；
char dir_op[4]={'u', 'd', 'r', 'l'};//对应上边四个方向的操作， 注意由于是反向求的， 所以方向对应相反；
void bfs(){node tmp;int a[10];for(int i=0; i<9; i++)a[i]=i+1;tmp.canto_val=canto_ex(a);tmp.pre=-1;tmp.pos=8;path[tmp.canto_val]="";int head, tail;head=tail=0;que[tail++]=tmp;vis[tmp.canto_val]=1;while(head<tail){tmp=que[head];int x, y, tx, ty, tpos, t_val;x=tmp.pos/3, y=tmp.pos%3;re_canto_ex(tmp.canto_val, a);for(int i=0; i<4; i++){tx=x+dir[i][0];ty=y+dir[i][1];tpos=tx*3+ty;	if(tx<0||ty<0||tx>=3||ty>=3) continue;swap(a[tmp.pos], a[tpos]);t_val=canto_ex(a);if(vis[t_val]){swap(a[tmp.pos], a[tpos]);//注意这里， 一定要再交换回来；continue;}node p;p.canto_val=t_val;p.pos=tpos;p.pre=tmp.canto_val;path[t_val]=dir_op[i]+path[tmp.canto_val];que[tail++]=p;vis[t_val]=1;swap(a[tmp.pos], a[tpos]);//同上， 交换回来；}head++;}
}
int main(){string s;memset(vis, 0, sizeof(vis));bfs();//打表；int a[10];while(getline(cin, s)){int j=0;for(int i=0; i<s.size(); i++){if(s[i]<='9'&&s[i]>='0') a[j++]=s[i]-'0';else if(s[i]=='x') a[j++]=9;}int ans=canto_ex(a);if(vis[ans]){cout << path[ans] << endl;}else cout << "unsolvable\n";}return 0;
}