hdu-1043 bfs+康拓展开hash

因为是计算还原成一种局面的最短步骤,应该想到从最终局面开始做bfs,把所有能到达的情况遍历一遍,把值存下来。

bfs过程中,访问过的局面的记录是此题的关键,9*9的方格在计算过程中直接存储非常占内存。而这个显然是12345678x的不同排列,考虑康拓展开来记录,每个局面hash成一个整数。步骤我先算了一下,最多有31步,我用4进制位hash成了两个整数来保存

#include <iostream>
#include <iomanip>
#include <set>
#include <cmath>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#define LL long long
using namespace std;
class cantor
{
public:
#define siz 9
char c[siz]={'','','','','','','','','x'};
LL w[siz];
bool vis[siz];
cantor()
{
w[]=;
for(int i=;i<siz;i++)
w[i]=w[i-]*i;
}
void init()
{
for(int i=;i<siz;i++)
vis[i]=false;
}
LL makeCanto(string s)
{
init();
LL rec=;
for(int i=;i<siz;i++)
{
int d=;
for(int j=;j<siz;j++)
{
if(vis[j])
continue;
if(c[j]!=s[i])d++;
else
{
vis[j]=true;
break;
}
}
rec+=w[siz-i-]*d;
}
return rec;
}
string recover(LL val)
{
init();
string s="";
for(int i=siz-;i>=;i--)
{
LL te=val/w[i];
val-=e*w[i];
for(int j=,cnt=-;j<siz;j++)
{
if(vis[j])continue;
else cnt++;
if(cnt==te&&!vis[j])
{
s+=c[j];
vis[j]=true;
break;
}
}
}
return s;
}
};
LL n,m;
char mp[][];
set<LL> s;
string ss="";
const string las="12345678x";
bool f;
int dir[][]={-,,,,,,,-};
char dfuck[]={'d','u','l','r'};
struct node
{
LL s;
int c;
int x,y;
LL a,b;
node(LL ss,int aa,int X,int Y,LL A,LL B){s=ss;c=aa;x=X;y=Y;a=A;b=B;}
};
struct ax
{
LL a,b,c;
ax(LL A,LL B,LL C){a=A;b=B;c=C;}
ax(){}
};
map<LL,ax> ans;
LL bit[];
int main()
{
cin.sync_with_stdio(false);
cantor fx;
bit[]=;
for(int i=;i<;i++)
bit[i]=bit[i-]*;
queue<node> q;
node ini=node(fx.makeCanto(las),,,,,);
q.push(ini);
s.clear();
ans.clear();
int mx=;
s.insert(fx.makeCanto(las));
while(!q.empty())
{
node now=q.front();
ans[now.s]=ax(now.a,now.b,now.c);
q.pop();
mx=max(now.c,mx);
for(int i=;i<;i++)
{
int yy=now.y+dir[i][];
int xx=now.x+dir[i][];
if(xx<||yy<||xx>=||yy>=)continue;
string nx=fx.recover(now.s);
swap(nx[now.y*+now.x],nx[yy*+xx]);
LL nxv=fx.makeCanto(nx);
if(s.find(nxv)!=s.end())continue;
s.insert(nxv);
LL na=now.a,nb=now.b;
if(now.c<)
{
na+=i*bit[now.c];
}
else
{
nb+=i*bit[now.c-];
}
q.push(node(nxv,now.c+,xx,yy,na,nb));
}
}
while(cin>>mp[][]>>mp[][]>>mp[][]>>mp[][]>>mp[][]>>mp[][]>>mp[][]>>mp[][]>>mp[][])
{
int x,y;
f=false;
s.clear();
ss="";
for(int i=;i<;i++)
for(int j=;j<;j++)
{
ss+=mp[i][j];
if(mp[i][j]=='x')
y=i,x=j;
}
string o="";
if(ss=="12345678x")
{
cout<<"lr"<<endl;
continue;
}
if(ans.find(fx.makeCanto(ss))==ans.end())
{
cout<<"unsolvable"<<endl;
continue;
}
ax fuck=ans[fx.makeCanto(ss)];
for(int i=;i<fuck.c;i++)
{
if(i<)
{
o+=dfuck[fuck.a%];
fuck.a/=;
}
else
{
o+=dfuck[fuck.b%];
fuck.b/=;
}
}
reverse(o.begin(),o.end());
cout<<o<<endl;
}
}

上一篇:Android自定义控件之自定义ViewGroup实现标签云


下一篇:一个fork()系统调用的问题