HDU 1043 Eight(反向BFS+打表+康托展开)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1043

题目大意:传统八数码问题

解题思路:就是从“12345678x”这个终点状态开始反向BFS,将各个状态记录下来,因为数字太大所以用康托展开将数字离散化。

代码:

 #include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
typedef long long ll;
const int N=4e5+; int vis[N];
string path[N];
char map[];
char index[]="udrl";//因为是逆向所以方向要反一下
int d[][]={{,},{-,},{,-},{,}};
int fac[]={,,,,,,,,}; struct node{
char num[];
int pos;
string path;
}pre,now; //求康托展开值
int cantor(char s[]){
int sum=;
int n=strlen(s);
for(int i=;i<n;i++){
int cnt=;
for(int j=i+;j<n;j++){
if(s[i]>s[j])
cnt++;
}
sum+=cnt*fac[n-i-];
}
return sum+;
}
//从12345678x逆向BFS打表
void bfs(){
queue<node>q;
now.pos=;
for(int i=;i<;i++)
now.num[i]=i++'';
now.num[]='';
now.num[]='\0';
q.push(now);
while(!q.empty()){
pre=q.front();
q.pop();
int pos=pre.pos;
//转换成二维坐标
int x=pos/;
int y=pos%;
for(int i=;i<;i++){
int xx=x+d[i][];
int yy=y+d[i][];
if(xx<||yy<||xx>||yy>)
continue;
//转换回一维坐标
int new_pos=xx*+yy;
now=pre;
swap(now.num[pos],now.num[new_pos]);
int tmp=cantor(now.num);
if(!vis[tmp]){
now.pos=new_pos;
//index[i]要加在前面,反的嘛
now.path=index[i]+now.path;
vis[tmp]=;
//存储路径
path[tmp]=now.path;
q.push(now);
}
}
}
} int main(){
char c;
bfs();
while(cin>>c){
//x转换成0便于康托展开
if(c=='x')
map[]='';
else
map[]=c;
for(int i=;i<;i++){
cin>>map[i];
if(map[i]=='x')
map[i]='';
}
int aim=cantor(map);
if(vis[aim])
cout<<path[aim]<<endl;
else
cout<<"unsolvable"<<endl;
}
}
上一篇:ZRender源码分析2:Storage(Model层)


下一篇:HDU1043 八数码(BFS + 打表)