八数码难题
一.广搜：
首先要考虑用什么存每一个状态
显然每个状态都用一个矩阵存是很麻烦的。
我们可以考虑将一个3*3的矩阵用一个字符串或long long 存。
每次扩展时再转化为矩阵。
另外一个问题是判重，对于已经搜过的状态，就不再扩展了。
10^9次方的bool数组会爆空间
可以考虑用hash
或者STL的map或set
//map 洛谷 8964ms
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
map<long long ,long long> m;
long long s,que[],head=,tail=;
long long c[][];
long long zx[]={,,,,-},
zy[]={,,-,,};
int main()
{
scanf("%lld",&s);
m[s]=;
que[head]=s;
while(head<=tail) //广搜
{
int x,y;
long long u=que[head++]; //取出队首元素
long long uu=u;
if(u==) break;
for(int i=;i<=;i++) //将long long型转化为矩阵
for(int j=;j<=;j++)
{
c[i][j]=uu%;
if(c[i][j]==){ //标记空格
x=i;
y=j;
}
uu/=;
}
for(int i=;i<=;i++)
{
long long xx=x+zx[i],yy=y+zy[i]; //向四个方向搜索
if(<=xx&&xx<=&&<=yy&&yy<=)
{
swap(c[x][y],c[xx][yy]);
long long l=;
for(int j=;j>=;j--)
for(int k=;k>=;k--)
l=l*+c[j][k]; //将扩展状态转化为长整形
map < long long ,long long > :: iterator it = m.find(l) ; //判重 map中的find函数用于寻找象所对应的原象（键值），若查找失败，返回最后一个键值位置
if(it==m.end()){
m[l]=m[u]+;
que[++tail]=l;
}
swap(c[x][y],c[xx][yy]);
}
}
}
printf("%lld\n",m[]);
return ;
}
//hash 洛谷 1080ms
#pragma GCC optimize(3)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MOD=;
long long s,que[],time[],head=,tail=;
long long c[][];
long long zx[]={,,,,-},
zy[]={,,-,,};
bool hashnum[];
inline bool hash(long long s)
{
long long h=,i=;
while(s)
{
i++;
long long k=s%;
s/=;
h=(h*i*+k)%MOD;
}
if(!hashnum[h]){
hashnum[h]=;
return ;
}
else return ;
}
int main()
{
scanf("%lld",&s);
que[head]=s;
while(head<=tail)
{
int x,y;
long long u=que[head++];
long long uu=u;if(u==) break;
for(register int i=;i<=;i++)
for(register int j=;j<=;j++)
{
c[i][j]=uu%;
if(c[i][j]==){
x=i;
y=j;
}
uu/=;
}
for(register int i=;i<=;i++)
{
long long xx=x+zx[i],yy=y+zy[i];
if(<=xx&&xx<=&&<=yy&&yy<=)
{
swap(c[x][y],c[xx][yy]);
long long l=;
for(int j=;j>=;j--)
for(int k=;k>=;k--)
l=l*+c[j][k];
if(hash(l)){
que[++tail]=l;
time[tail]=time[head-]+;
}
swap(c[x][y],c[xx][yy]);
}
}
}
printf("%lld\n",time[head-]);
return ;
}
二、启发式搜索
估价函数：
close[i]=time[i]+cym[i]
time[i]是搜到当前状态已经用的时间
cym[i]表示每个数字到目标状态的曼哈顿距离之和/2
可以看出，close[i]是小于实际步数的，所以搜起来效率高些
//启发式搜索 420ms
#pragma GCC optimize(3)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int MOD=;
long long s,num;
long long data[];
int time[];
int close[];
struct cmp
{
bool operator()(int a,int b)
{
return close[a]>close[b];
}
};
priority_queue<int,vector<int>,cmp> que;
long long c[][];
long long zx[]={,,,,-},
zy[]={,,-,,};
bool hashnum[];
inline bool hash(long long s)
{
long long h=,i=;
while(s)
{
i++;
long long k=s%;
s/=;
h=(h*i*+k)%MOD;
}
if(!hashnum[h]){
hashnum[h]=;
return ;
}
else return ;
}
int de[][]={{,},{,},{,},{,},{,},{,},{,},{,},{,}};
inline int cym(long long tt) //个位数字的笛卡尔距离之和
{
int nn[][];
for(register int i=;i<;i++)
for(register int j=;j<;j++)
{
nn[-i][-j]=tt%;
tt/=;
}
int mark=;
for(register int i=;i<=;i++)
for(register int j=;j<=;j++)
mark+=abs(i-de[nn[i][j]][])+abs(j-de[nn[i][j]][]);
return mark>>1;
}
int main()
{
scanf("%lld",&s);
data[++num]=s;
close[num]=cym(s);
que.push(num);
int u;
while(!que.empty())
{
int x,y;
u=que.top(); //每次取估价最小的元素
que.pop();
long long uu=data[u];if(uu==) break;
for(register int i=;i<=;i++)
for(register int j=;j<=;j++)
{
c[i][j]=uu%;
if(c[i][j]==){
x=i;
y=j;
}
uu/=;
}
for(register int i=;i<=;i++)
{
long long xx=x+zx[i],yy=y+zy[i];
if(<=xx&&xx<=&&<=yy&&yy<=)
{
swap(c[x][y],c[xx][yy]);
long long l=;
for(int j=;j>=;j--)
for(int k=;k>=;k--)
l=l*+c[j][k];
if(hash(l)){
data[++num]=l;
time[num]=time[u]+;
close[num]=cym(l)+time[num]; //估价
que.push(num);
}
swap(c[x][y],c[xx][yy]);
}
}
}
printf("%lld\n",time[u]);
return ;
}