2019.3.9 kuangbin训练 hdu1043(康托展开 A* bfs打表)
hdu1043
题意：
给一个八数码的棋盘信息，x表示空格
判断能否拼出，并打印步骤
题解：
2种做法
1.康托展开+逆康托展开+bfs逆向打表
康托展开简单介绍：
可以将长度为n的不同数字组合，映射到其全排列的下标（从0开始）
例如：
｛1，2，3，4｝–> 0
｛1，2，4，3｝–> 1
…
｛4，3，2，1｝–> 23
逆康托展开简单介绍：
给出康托展开的映射值和长度n，还原不同的数字组合
例如：
0 —> ｛1，2，3，4｝
1 —> ｛1，2，4，3｝
…
23 —>｛4，3，2，1｝
因为最终状态只有1个Final[] =｛1，2，3，4，5，6，7，8，9｝（我把空格当成9）
所以可以从Final往回搜索，找出所有存在的局面
用康托展开的映射值key作为标识方便储存
然后bfs打表就行了
代码：
#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <queue>
using namespace std;
const int maxn=370000;
char s[5];
int m[10],fac[10];
int Final[]={1,2,3,4,5,6,7,8,9};
int X[]={-1,0,1,0};
int Y[]={0,1,0,-1};
int vis[maxn];
char ans[maxn][50];
struct node
{
int key,x,y;
node(int kk,int xx,int yy):key(kk),x(xx),y(yy){}
};
void init()
{
fac[0]=1;
for(int i=1;i<10;i++)
fac[i]=fac[i-1]*i;
}
int cantor(int a[],int len)
{
int pos=0;
for(int i=0;i<len;i++)
{
int cnt=0;
for(int j=i+1;j<len;j++)
if(a[i]>a[j])
cnt++;
pos+=cnt*fac[len-i-1];
}
return pos;
}
int res[10];
void decantor(int pos,int len)
{
int hash[10]={0};
int temp;
for(int i=0;i<len;i++)
{
temp=pos/fac[len-i-1];
for(int j=0;j<=temp;j++)
if(hash[j])
temp++;
res[i]=temp+1;
hash[temp]=1;
pos=pos%fac[len-i-1];
}
}
void bfs()
{
queue<node> q;
while(!q.empty()) q.pop();
int key=cantor(Final,9);
q.push(node(key,2,2));
vis[key]=1;
ans[key][0]='\0';
while(!q.empty())
{
node temp=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int nx=temp.x+X[i];
int ny=temp.y+Y[i];
if(nx<0 || nx>=3 || ny<0 || ny>=3)
continue;
decantor(temp.key,9);
swap(res[nx*3+ny],res[temp.x*3+temp.y]);
/* for(int j=0;j<9;j++) printf("%d ",res[j]); printf("\n"); */
int nkey=cantor(res,9);
//printf("reskey = %d (%d,%d)\n",key,nx,ny);
if(!vis[nkey])
{
vis[nkey]=1;
q.push(node(nkey,nx,ny));
//strcpy(ans[key]+1,ans[temp.key]);
if(i==0) ans[nkey][0]='d';
if(i==1) ans[nkey][0]='l';
if(i==2) ans[nkey][0]='u';
if(i==3) ans[nkey][0]='r';
int k=0;
while(ans[temp.key][k])
{
ans[nkey][k+1]=ans[temp.key][k];
k++;
}
ans[nkey][k+1]='\0';
}
}
}
}
int main()
{
init();
bfs();
while(scanf("%s",s)!=EOF)
{
int k=0;
if(s[0]=='x')
m[k++]=9;
else m[k++]=s[0]-'0';
for(int i=1;i<=8;i++)
{
scanf("%s",s);
if(s[0]=='x')
m[k++]=9;
else m[k++]=s[0]-'0';
}
int key=cantor(m,9);
if(vis[key])
printf("%s\n",ans[key]);
else printf("unsolvable\n");
}
return 0;
}
2.康托展开+奇偶性判断剪枝+A搜索
方法1是逆向的，方法2是正向的
A搜索的估计函数h（x）用每个数字到Final的曼哈顿距离之和衡量
代码：
#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
const int maxn=370000;
int T,kase;
char s[9];
int a[9],x_a,y_a,tg[9]={1,2,3,4,5,6,7,8,9};
int fac[9];
int X[]={1,0,0,-1};
int Y[]={0,-1,1,0};
int target;
int vis[maxn];
char ans[107],ch[maxn];
int pre[maxn];
char S[]={'d','l','r','u'};
struct node
{
int a[9];
int key,x,y;
int g,h;
node(int *aa,int kk,int xx,int yy,int gg,int hh)
{
key=kk;x=xx;y=yy;g=gg;h=hh;
for(int i=0;i<9;i++)
a[i]=aa[i];
}
bool operator < (const node &a) const
{
return (g+h)>(a.g+a.h);
}
};
void init()
{
fac[0]=1;
for(int i=1;i<9;i++)
fac[i]=fac[i-1]*i;
}
int cantor(int a[],int len)
{
int pos=0;
for(int i=0;i<len;i++)
{
int cnt=0;
for(int j=i+1;j<len;j++)
if(a[i]>a[j])
cnt++;
pos+=cnt*fac[len-i-1];
}
return pos;
}
int stdx[]={0,0,0,1,1,1,2,2,2};
int stdy[]={0,1,2,0,1,2,0,1,2};
int geth(int *a)
{
int h=0;
for(int i=0;i<9;i++)
if(a[i]!=9)
h+=abs(i/3-stdx[a[i]-1])+abs(i%3-stdy[a[i]-1]);
return h;
}
void bfs()
{
priority_queue<node> q;
while(!q.empty()) q.pop();
int key=cantor(a,9);
q.push(node(a,key,x_a,y_a,0,geth(a)));
vis[key]=1;
pre[key]=-1;
while(!q.empty())
{
node temp=q.top();
q.pop();
if(temp.key==target)
{
int cnt=0;
int k=target;
while(pre[k]!=-1)
{
ans[cnt++]=ch[k];
k=pre[k];
}
for(int i=cnt-1;i>=0;i--)
printf("%c",ans[i]);
printf("\n");
return;
}
for(int i=0;i<4;i++)
{
int nx=temp.x+X[i];
int ny=temp.y+Y[i];
if(nx<0 || nx>=3 || ny<0 || ny>=3)
continue;
int na[9];
for(int j=0;j<9;j++)
na[j]=temp.a[j];
swap(na[nx*3+ny],na[temp.x*3+temp.y]);
int nkey=cantor(na,9);
if(!vis[nkey])
{
vis[nkey]=1;
pre[nkey]=temp.key;
ch[nkey]=S[i];
q.push(node(na,nkey,nx,ny,temp.g+1,geth(na)));
}
}
}
}
int main()
{
init();
while(scanf("%s",s)!=EOF)
{
if(s[0]=='x')
{
a[0]=9;
x_a=0;
y_a=0;
}
else a[0]=s[0]-'0';
for(int i=1;i<=8;i++)
{
scanf("%s",s);
if(s[0]=='x')
{
a[i]=9;
x_a=i/3;
y_a=i%3;
}
else a[i]=s[0]-'0';
}
int cnt=0;
for(int i=0;i<9;i++)
for(int j=i+1;j<9;j++)
if(a[i]!=9 && a[i]>a[j])
cnt++;
if(cnt%2)
{
printf("unsolvable\n");
}
else
{
memset(vis,0,sizeof(vis));
memset(ans,0,sizeof(ans));
target=cantor(tg,9);
bfs();
}
}
return 0;
}
哔哩哔哩公司福利 424人发布
