八数码问题。用hash（康托展开）判重
bfs(TLE)
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int fac[]={,,,,,,,,,};
bool hash_map[];
int data[][];
queue<int> q;
//data[][9]存储上一个状态，data[][10]存储到这个状态的操作,data[][11]存储这个状态中9的位置
char s[];
int mem;
int hash1(int s[])
{
int i,j,cnt,sum=;
for(i=;i<;i++)
{
cnt=;
for(j=i+;j<;j++)
if(s[j]<s[i])
cnt++;
sum+=cnt*fac[-i];
}
return sum;
}
void print(int x)
{
if(data[x][]==) return;
print(data[x][]);
if(data[x][]==)
putchar('l');
else if(data[x][]==)
putchar('r');
else if(data[x][]==)
putchar('u');
else putchar('d');
}
int main()
{
char ch;
int i,j,a,b,t,p;
while(cin.getline(s,))
{
memset(data,,sizeof(data));
memset(hash_map,,sizeof(hash_map));
b=mem=;
j=;
for(i=;s[i]!='\0';i++)
{
if(s[i]==' ') continue;
sscanf(s+i,"%c",&ch);
if(ch=='x')
{
data[b][j]=;
data[b][]=j++;
}
else
data[b][j++]=ch-'';
}
q.push(b);
t=hash1(data[b]);
hash_map[t]=true;
if(t==)
goto xxx;
while(!q.empty())
{
a=q.front();
q.pop();
p=data[a][];
if(p!=&&p!=&&p!=)
{
memcpy(data[],data[a],sizeof(data[]));
t=data[][p];
data[][p]=data[][p-];
data[][p-]=t;
data[][]=a;
data[][]=;
data[][]=p-;
t=hash1(data[]);
if(hash_map[t]==false)
{
if(t==)
{
print();
goto xxx;
}
hash_map[t]=true;
b=++mem;
memcpy(data[b],data[],sizeof(data[b]));
q.push(b);
}
}
if(p!=&&p!=&&p!=)
{
memcpy(data[],data[a],sizeof(data[]));
t=data[][p];
data[][p]=data[][p+];
data[][p+]=t;
data[][]=a;
data[][]=;
data[][]=p+;
t=hash1(data[]);
if(hash_map[t]==false)
{
if(t==)
{
print();
goto xxx;
}
hash_map[t]=true;
b=++mem;
memcpy(data[b],data[],sizeof(data[b]));
q.push(b);
}
}
if(p>)
{
memcpy(data[],data[a],sizeof(data[]));
t=data[][p];
data[][p]=data[][p-];
data[][p-]=t;
data[][]=a;
data[][]=;
data[][]=p-;
t=hash1(data[]);
if(hash_map[t]==false)
{
if(t==)
{
print();
goto xxx;
}
hash_map[t]=true;
b=++mem;
memcpy(data[b],data[],sizeof(data[b]));
q.push(b);
}
}
if(p<)
{
memcpy(data[],data[a],sizeof(data[]));
t=data[][p];
data[][p]=data[][p+];
data[][p+]=t;
data[][]=a;
data[][]=;
data[][]=p+;
t=hash1(data[]);
if(hash_map[t]==false)
{
if(t==)
{
print();
goto xxx;
}
hash_map[t]=true;
b=++mem;
memcpy(data[b],data[],sizeof(data[b]));
q.push(b);
}
}
}
printf("unsolvable");
xxx:
puts("");
while(!q.empty()) q.pop();
memset(s,,sizeof(s));
}
return ;
}
从目标状态出发，一次bfs打出所有输入对应结果的表(172ms)
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int fac[]={,,,,,,,,,};
bool hash_map[];
int data[][];
int temp[];
queue<int> q;
//data[][9]存储上一个状态，data[][10]存储到这个状态的操作,data[][11]存储这个状态中9的位置
char s[];
int mem;
int hash1(int s[])
{
int i,j,cnt,sum=;
for(i=;i<;i++)
{
cnt=;
for(j=i+;j<;j++)
if(s[j]<s[i])
cnt++;
sum+=cnt*fac[-i];
}
return sum;
}
void print(int x)
{
if(x==)
putchar('r');
else if(x==)
putchar('l');
else if(x==)
putchar('d');
else putchar('u');
}
void init()
{
int i,a,b,p,t;
q.push();
for(i=;i<;i++)
data[][i]=i+;
data[][]=;
hash_map[]=;
while(!q.empty())
{
a=q.front();
q.pop();
p=data[a][];
if(p%!=)
{
memcpy(temp,data[a],sizeof(temp));
t=temp[p];
temp[p]=temp[p-];
temp[p-]=t;
temp[]=a;
temp[]=;
temp[]=p-;
t=hash1(temp);
if(!hash_map[t])
{
hash_map[t]=;
memcpy(data[t],temp,sizeof(data[t]));
q.push(t);
}
}
if(p%!=)
{
memcpy(temp,data[a],sizeof(temp));
t=temp[p];
temp[p]=temp[p+];
temp[p+]=t;
temp[]=a;
temp[]=;
temp[]=p+;
t=hash1(temp);
if(!hash_map[t])
{
hash_map[t]=;
memcpy(data[t],temp,sizeof(data[t]));
q.push(t);
}
}
if(p>)
{
memcpy(temp,data[a],sizeof(temp));
t=temp[p];
temp[p]=temp[p-];
temp[p-]=t;
temp[]=a;
temp[]=;
temp[]=p-;
t=hash1(temp);
if(!hash_map[t])
{
hash_map[t]=;
memcpy(data[t],temp,sizeof(data[t]));
q.push(t);
}
}
if(p<)
{
memcpy(temp,data[a],sizeof(temp));
t=temp[p];
temp[p]=temp[p+];
temp[p+]=t;
temp[]=a;
temp[]=;
temp[]=p+;
t=hash1(temp);
if(!hash_map[t])
{
hash_map[t]=;
memcpy(data[t],temp,sizeof(data[t]));
q.push(t);
}
}
}
}
int main()
{
char ch;
int i,j,t,p;
init();
while(cin.getline(s,))
{
j=;
for(i=;s[i]!='\0';i++)
{
if(s[i]==' ') continue;
sscanf(s+i,"%c",&ch);
if(ch=='x')
{
temp[j]=;
temp[]=j++;
}
else
temp[j++]=ch-'';
}
t=hash1(temp);
if(!hash_map[t])
puts("unsolvable");
else
{
for(i=t;i!=;i=data[i][])
print(data[i][]);
puts("");
}
}
return ;
}
以下的IDA*和A*都要用逆序数特判无解的情况，因为无解的时候IDA*直接无限制搜，A*遍历所有解空间，效率很低。
所谓逆序数判无解态是因为两个能够互相移动成的状态的逆序数的奇偶性是相同的。
IDA*(266ms)，估价函数是“所有不为x的方块与目标位置的曼哈顿距离之和”，因为每次移动最多减少一点这个的值
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> P;
int fac[]={,,,,,,,,,};
int dat[];
char s[];
char ans[];
int maxd;
int fx[]={,,,,,,,,,};
int fy[]={,,,,,,,,,};
bool fl;
int abs(int x)
{
if(x>) return x;
else return -x;
}
int h()
{
int ans=,i;
for(i=;i<;i++)
if(dat[i]!=)
ans+=abs(i/-fx[dat[i]])+abs(i%-fy[dat[i]]);
return ans;
}
int hash1(int s[])
{
int i,j,cnt,sum=;
for(i=;i<;i++)
{
cnt=;
for(j=i+;j<;j++)
if(s[j]<s[i])
cnt++;
sum+=cnt*fac[-i];
}
return sum;
}
bool inverse(int ss[])
{
int t=,x,y;
for(int i=;i<;i++)
for(int j=;j<i;j++)
{
if(ss[i]==||ss[j]==)continue;
x=ss[j];
y=ss[i];
if(x>y)
t++;
}
if(t&)
return true;
return false;
}
bool check()
{
for(int i=;i<;i++)
if(dat[i]!=i+)
return ;
return ;
}
void dfs(int now,int dep)
{
if(dep==maxd)
{
if(check()) fl=;
return;
}
if(h()+dep>maxd) return;
if(fl) return;
if(now%!=)
{
swap(dat[now],dat[now-]);
ans[dep]='l';
dfs(now-,dep+);
swap(dat[now],dat[now-]);
}
if(fl) return;
if(now%!=)
{
swap(dat[now],dat[now+]);
ans[dep]='r';
dfs(now+,dep+);
swap(dat[now],dat[now+]);
}
if(fl) return;
if(now>)
{
swap(dat[now],dat[now-]);
ans[dep]='u';
dfs(now-,dep+);
swap(dat[now],dat[now-]);
}
if(fl) return;
if(now<)
{
swap(dat[now],dat[now+]);
ans[dep]='d';
dfs(now+,dep+);
swap(dat[now],dat[now+]);
}
}
int main()
{
char ch;
int i,j,st;
while(cin.getline(s,))
{
memset(dat,,sizeof(dat));
j=;
for(i=;s[i]!='\0';i++)
{
if(s[i]==' ') continue;
sscanf(s+i,"%c",&ch);
if(ch=='x')
{
dat[j]=;
st=j++;
}
else
dat[j++]=ch-'';
}
if(inverse(dat))
{
printf("unsolvable");
goto xxx;
}
if(hash1(dat)==)
goto xxx;
fl=;
for(maxd=;!fl;++maxd)
dfs(st,);
for(i=;i<maxd;i++)
putchar(ans[i]);
xxx:
puts("");
}
return ;
}
A*(141ms)，用了比较naive的估价函数，x与目标位置的曼哈顿距离
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> P;
int fac[]={,,,,,,,,,};
bool hash_map[];
int dat[][];
priority_queue<P,vector<P>,greater<P> > q;
//dat[][9]存储上一个状态，dat[][10]存储到这个状态的操作,dat[][11]存储这个状态中9的位置,dat[][12]存储到这个状态的步数
char s[];
int h[]={,,,,,,,,};
int mem;
int hash1(int s[])
{
int i,j,cnt,sum=;
for(i=;i<;i++)
{
cnt=;
for(j=i+;j<;j++)
if(s[j]<s[i])
cnt++;
sum+=cnt*fac[-i];
}
return sum;
}
void print(int x)
{
if(dat[x][]==) return;
print(dat[x][]);
if(dat[x][]==)
putchar('l');
else if(dat[x][]==)
putchar('r');
else if(dat[x][]==)
putchar('u');
else putchar('d');
} bool inverse(int ss[])
{
int t=,x,y;
for(int i=;i<;i++)
for(int j=;j<i;j++)
{
if(ss[i]==||ss[j]==)continue;
x=ss[j];
y=ss[i];
if(x>y)
t++;
}
if(t&)
return true;
return false;
} int main()
{
char ch;
int i,j,a,b,t,p;
while(cin.getline(s,))
{
memset(dat,,sizeof(dat));
memset(hash_map,,sizeof(hash_map));
b=mem=;
j=;
for(i=;s[i]!='\0';i++)
{
if(s[i]==' ') continue;
sscanf(s+i,"%c",&ch);
if(ch=='x')
{
dat[b][j]=;
dat[b][]=j++;
}
else
dat[b][j++]=ch-'';
}
q.push(P(h[dat[b][]],b));
t=hash1(dat[b]);
hash_map[t]=true;
if(inverse(dat[b]))
{
printf("unsolvable");
goto xxx;
}
if(t==)
goto xxx;
while(!q.empty())
{
a=q.top().second;
q.pop();
p=dat[a][];
if(p!=&&p!=&&p!=)
{
memcpy(dat[],dat[a],sizeof(dat[]));
t=dat[][p];
dat[][p]=dat[][p-];
dat[][p-]=t;
dat[][]=a;
dat[][]=;
dat[][]=p-;
dat[][]=dat[p][]+;
t=hash1(dat[]);
if(hash_map[t]==false)
{
if(t==)
{
print();
goto xxx;
}
hash_map[t]=true;
b=++mem;
memcpy(dat[b],dat[],sizeof(dat[b]));
q.push(P(dat[b][]+h[dat[b][]],b));
}
}
if(p!=&&p!=&&p!=)
{
memcpy(dat[],dat[a],sizeof(dat[]));
t=dat[][p];
dat[][p]=dat[][p+];
dat[][p+]=t;
dat[][]=a;
dat[][]=;
dat[][]=p+;
dat[][]=dat[p][]+;
t=hash1(dat[]);
if(hash_map[t]==false)
{
if(t==)
{
print();
goto xxx;
}
hash_map[t]=true;
b=++mem;
memcpy(dat[b],dat[],sizeof(dat[b]));
q.push(P(dat[b][]+h[dat[b][]],b));
}
}
if(p>)
{
memcpy(dat[],dat[a],sizeof(dat[]));
t=dat[][p];
dat[][p]=dat[][p-];
dat[][p-]=t;
dat[][]=a;
dat[][]=;
dat[][]=p-;
dat[][]=dat[p][]+;
t=hash1(dat[]);
if(hash_map[t]==false)
{
if(t==)
{
print();
goto xxx;
}
hash_map[t]=true;
b=++mem;
memcpy(dat[b],dat[],sizeof(dat[b]));
q.push(P(dat[b][]+h[dat[b][]],b));
}
}
if(p<)
{
memcpy(dat[],dat[a],sizeof(dat[]));
t=dat[][p];
dat[][p]=dat[][p+];
dat[][p+]=t;
dat[][]=a;
dat[][]=;
dat[][]=p+;
dat[][]=dat[p][]+;
t=hash1(dat[]);
if(hash_map[t]==false)
{
if(t==)
{
print();
goto xxx;
}
hash_map[t]=true;
b=++mem;
memcpy(dat[b],dat[],sizeof(dat[b]));
q.push(P(dat[b][]+h[dat[b][]],b));
}
}
}
xxx:
puts("");
while(!q.empty()) q.pop();
memset(s,,sizeof(s));
}
return ;
}
A*(16ms)，估价函数同IDA*
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> P;
int fac[]={,,,,,,,,,};
bool hash_map[];
int dat[][];
priority_queue<P,vector<P>,greater<P> > q;
//dat[][9]存储上一个状态，dat[][10]存储到这个状态的操作,dat[][11]存储这个状态中9的位置,dat[][12]存储到这个状态的步数
char s[];
int fx[]={,,,,,,,,,};
int fy[]={,,,,,,,,,};
int abs(int x)
{
if(x>) return x;
else return -x;
}
int h(int b)
{
int ans=,i;
for(i=;i<;i++)
if(dat[b][i]!=)
ans+=abs(i/-fx[dat[b][i]])+abs(i%-fy[dat[b][i]]);
return ans;
}
int mem;
int hash1(int s[])
{
int i,j,cnt,sum=;
for(i=;i<;i++)
{
cnt=;
for(j=i+;j<;j++)
if(s[j]<s[i])
cnt++;
sum+=cnt*fac[-i];
}
return sum;
}
void print(int x)
{
if(dat[x][]==) return;
print(dat[x][]);
if(dat[x][]==)
putchar('l');
else if(dat[x][]==)
putchar('r');
else if(dat[x][]==)
putchar('u');
else putchar('d');
} bool inverse(int ss[])
{
int t=,x,y;
for(int i=;i<;i++)
for(int j=;j<i;j++)
{
if(ss[i]==||ss[j]==)continue;
x=ss[j];
y=ss[i];
if(x>y)
t++;
}
if(t&)
return true;
return false;
} int main()
{
char ch;
int i,j,a,b,t,p;
while(cin.getline(s,))
{
memset(dat,,sizeof(dat));
memset(hash_map,,sizeof(hash_map));
b=mem=;
j=;
for(i=;s[i]!='\0';i++)
{
if(s[i]==' ') continue;
sscanf(s+i,"%c",&ch);
if(ch=='x')
{
dat[b][j]=;
dat[b][]=j++;
}
else
dat[b][j++]=ch-'';
}
q.push(P(h(b),b));
t=hash1(dat[b]);
hash_map[t]=true;
if(inverse(dat[b]))
{
printf("unsolvable");
goto xxx;
}
if(t==)
goto xxx;
while(!q.empty())
{
a=q.top().second;
q.pop();
p=dat[a][];
if(p!=&&p!=&&p!=)
{
memcpy(dat[],dat[a],sizeof(dat[]));
t=dat[][p];
dat[][p]=dat[][p-];
dat[][p-]=t;
dat[][]=a;
dat[][]=;
dat[][]=p-;
dat[][]=dat[p][]+;
t=hash1(dat[]);
if(hash_map[t]==false)
{
if(t==)
{
print();
goto xxx;
}
hash_map[t]=true;
b=++mem;
memcpy(dat[b],dat[],sizeof(dat[b]));
q.push(P(dat[b][]+h(b),b));
}
}
if(p!=&&p!=&&p!=)
{
memcpy(dat[],dat[a],sizeof(dat[]));
t=dat[][p];
dat[][p]=dat[][p+];
dat[][p+]=t;
dat[][]=a;
dat[][]=;
dat[][]=p+;
dat[][]=dat[p][]+;
t=hash1(dat[]);
if(hash_map[t]==false)
{
if(t==)
{
print();
goto xxx;
}
hash_map[t]=true;
b=++mem;
memcpy(dat[b],dat[],sizeof(dat[b]));
q.push(P(dat[b][]+h(b),b));
}
}
if(p>)
{
memcpy(dat[],dat[a],sizeof(dat[]));
t=dat[][p];
dat[][p]=dat[][p-];
dat[][p-]=t;
dat[][]=a;
dat[][]=;
dat[][]=p-;
dat[][]=dat[p][]+;
t=hash1(dat[]);
if(hash_map[t]==false)
{
if(t==)
{
print();
goto xxx;
}
hash_map[t]=true;
b=++mem;
memcpy(dat[b],dat[],sizeof(dat[b]));
q.push(P(dat[b][]+h(b),b));
}
}
if(p<)
{
memcpy(dat[],dat[a],sizeof(dat[]));
t=dat[][p];
dat[][p]=dat[][p+];
dat[][p+]=t;
dat[][]=a;
dat[][]=;
dat[][]=p+;
dat[][]=dat[p][]+;
t=hash1(dat[]);
if(hash_map[t]==false)
{
if(t==)
{
print();
goto xxx;
}
hash_map[t]=true;
b=++mem;
memcpy(dat[b],dat[],sizeof(dat[b]));
q.push(P(dat[b][]+h(b),b));
}
}
}
xxx:
puts("");
while(!q.empty()) q.pop();
memset(s,,sizeof(s));
}
return ;
}
A*(79ms)，假的估价函数(fx,fy前面少加了一个0)
int fx[]={,,,,,,,,};
int fy[]={,,,,,,,,};