题目链接
https://www.luogu.org/problemnew/show/P1379
分析
经典的八数码问题,有双向BFS和(IDA*)的方法，这里使用的是(A*)启发式搜索.
简要介绍一下(A*),就是对于搜索的每一个状态设计一个评估函数(f(state)),表示当前状态(state)到目标状态所需代价的估计值;还有一个(g(state)),表示当前状态(state)到目标状态实际需要的最小代价,(A*)中必须保证(f(state)<=g(state))才能确保在目标状态第一次被取出时就是最优解（实际一点,比如最少的步数）并且在搜索中每个状态只需扩展一次，设计的估价函数(f(stste))越接近(g(state))效率越高.
我们这里用曼哈顿距离设计估价函数，也就是(f(state)=)$sum^9_{i=1} (|posx_i-goalx_i|+|posy_i-goaly_i|) $
(posx_i)表示(i)这个数字在九宫格中的横坐标,(posy_i)也就类似的。注意,我们不能统计(0)，否则这样(f(state))可能会大于实际代价
为了确保每个状态都被拓展一次，我们可以采用康托展开(将(1-n)的全排列映射成(1-n!)中的一个数)或是哈希表(unordered_map/pb_ds::gp_hash_table/map)
同时还要注意,八数码问题有时候是没有解的,我们将九宫格除空格之外的数按从左到右,再从上到下的顺序排成一列数来表示每一个状态，如果初始状态和目标状态的逆序对个数奇偶性不同的话是无解的,可以提前判断一下是否有解来提高效率
题目:
P1379 八数码难题
题目链接：https://www.luogu.org/problemnew/show/P1379
非常简单,甚至不用判断无解
代码:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#include <utility>
#include <cmath>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define ll long long
#define ri register int
#define ull unsigned long long
using std::pair;
using std::swap;
using std::abs;
using std::priority_queue;
using namespace __gnu_pbds;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;return ;
}
const int maxn=5;
const int inf=0x7fffffff;
const int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
int sta[maxn][maxn];
ll st,goal;
gp_hash_table <ll,bool>g;
pair<int,int>pos[10];
struct Sta{
ll a;
int s,f;
Sta(){;}
Sta(ll _a,int _s,int _f){a=_a,s=_s,f=_f;}
bool operator <(const Sta &b)const{
return f>b.f;
}
};
int bx,by;//0位置
inline int get_f(){//估价函数
int ans=0;
for(ri i=1;i<=3;i++){
for(ri j=1;j<=3;j++){
if(state[i][j])ans+=abs(i-pos[sta[i][j]].first)+abs(j-pos[sta[i][j]].second);
}
}
return ans;
}
inline ll turn_num(){//转为数字
ll ans=0;
for(ri i=1;i<=3;i++){
for(ri j=1;j<=3;j++){
ans=ans*10+sta[i][j];
}
}
return ans;
}
inline void turn_sta(ll num){//转为九宫格
for(ri i=3;i>=1;i--){
for(ri j=3;j>=1;j--){
sta[i][j]=num%10;
num=num/10;
if(!sta[i][j])bx=i,by=j;
}
}
return ;
}
inline void astar(){
ll now,nxt;
int x,y,z;
Sta tmp;
priority_queue<Sta>q;
while(q.size())q.pop();
turn_sta(st);
q.push(Sta(st,0,get_f()));
g[st]=1;
while(q.size()){
tmp=q.top();q.pop();
now=tmp.a,z=tmp.s;
if(now==goal){
printf("%d
",z);
return ;
}
turn_sta(now);
for(ri i=0;i<4;i++){
x=bx+dx[i],y=by+dy[i];
if(x>=1&&x<=3&&y>=1&&y<=3){
swap(sta[bx][by],sta[x][y]);
nxt=turn_num();
if(g[nxt]){
swap(sta[bx][by],sta[x][y]);
continue;
}
g[nxt]=1;
q.push(Sta(nxt,z+1,z+1+get_f()));
swap(sta[bx][by],sta[x][y]);
}
}
}
puts("unsolvable");
return ;
}
int main(){
/*230187546*/
int x,y,z;
pos[0].first=2,pos[0].second=2;
pos[1].first=1,pos[1].second=1;
pos[2].first=1,pos[2].second=2;
pos[3].first=1,pos[3].second=3;
pos[4].first=2,pos[4].second=3;
pos[5].first=3,pos[5].second=3;
pos[6].first=3,pos[6].second=2;
pos[7].first=3,pos[7].second=1;
pos[8].first=2,pos[8].second=1;
read(st);
goal=123804765;
astar();
return 0;
}
POJ1077 Eight
题目链接:http://poj.org/problem?id=1077
要打印方案,我用了一个(naive)的方法,就是记录每个状态是从哪个状态转移过来的((A*)保证扩展到每一个状态时一定是花费最少的步数)，同时再用一个哈希表记录它是进行哪个操作转移过来的，最后递归打印即可
当然还有其他方法这里不赘述.由于POJ好像不资瓷pbds和unordered_map,只好用map
代码:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#include <utility>
#include <cmath>
#include <map>
#define ll long long
#define ri register int
#define ull unsigned long long
using namespace std;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;return ;
}
const int maxn=5;
const int inf=0x7fffffff;
const int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
const char ch[4]={'u','l','r','d'};
int sta[maxn][maxn];
ll st,goal;
map <ll,ll> pre;
map <ll,int> dir;
pair<int,int>pos[10];
struct Sta{
ll a;
int s,f;
Sta(){;}
Sta(ll _a,int _s,int _f){a=_a,s=_s,f=_f;}
bool operator <(const Sta &b)const{
return f>b.f;
}
};
int bx,by;//0位置
inline int get_f(){
int ans=0;
for(ri i=1;i<=3;i++){
for(ri j=1;j<=3;j++){
if(sta[i][j]==0)continue;
ans+=abs(i-pos[sta[i][j]].first)+abs(j-pos[sta[i][j]].second);
}
}
return ans;
}
inline ll turn_num(){
ll ans=0;
for(ri i=1;i<=3;i++){
for(ri j=1;j<=3;j++){
ans=ans*10+sta[i][j];
}
}
return ans;
}
inline void turn_sta(ll num){
for(ri i=3;i>=1;i--){
for(ri j=3;j>=1;j--){
sta[i][j]=num%10;
num=num/10;
if(!sta[i][j])bx=i,by=j;
}
}
return ;
}
void print(ll x){
/*234150768*/
if(x==st)return ;
print(pre[x]);
putchar(ch[dir[x]]);
return ;
}
inline void astar(){
ll now,nxt;
int x,y,z;
Sta tmp;
priority_queue<Sta>q;
while(q.size())q.pop();//puts("wtf");
turn_sta(st);
q.push(Sta(st,0,get_f()));
while(q.size()){
tmp=q.top();q.pop();
now=tmp.a,z=tmp.s;
if(now==goal){
//printf("%d
",z);
//printf("%lld***
***",pre[st]);
print(goal);
return ;
}
//printf("*%lld
",now);
turn_sta(now);
for(ri i=0;i<4;i++){
x=bx+dx[i],y=by+dy[i];
if(x>=1&&x<=3&&y>=1&&y<=3){
swap(sta[bx][by],sta[x][y]);
nxt=turn_num();
if(!pre[nxt]){
pre[nxt]=now;
dir[nxt]=i;
q.push(Sta(nxt,z+1,z+1+get_f()));
}
swap(sta[bx][by],sta[x][y]);
}
}
}
puts("unsolvable");
return ;
}
int main(){
int num[10];
char x[2];
pos[0].first=3,pos[0].second=3;
pos[1].first=1,pos[1].second=1;
pos[2].first=1,pos[2].second=2;
pos[3].first=1,pos[3].second=3;
pos[4].first=2,pos[4].second=1;
pos[5].first=2,pos[5].second=2;
pos[6].first=2,pos[6].second=3;
pos[7].first=3,pos[7].second=1;
pos[8].first=3,pos[8].second=2;
//read(st);
st=0;
for(ri i=1;i<=9;i++){
scanf("%s",x);
if(x[0]=='x')st=st*10,num[i]=inf;
else st=st*10+x[0]-'0',num[i]=x[0]-'0';
}
//printf("%lld
",st);
int cnt=0;
for(ri i=1;i<=9;i++){
if(num[i]==inf)continue;
for(ri j=i+1;j<=9;j++){
if(num[j]<num[i]){cnt++;}
}
}
//printf("%d
",cnt);
if(cnt%2==1){
puts("unsolvable");
}
else{
pre[st]=19260817;
goal=123456780;
astar();
}
return 0;
}
UVA652 Eight
题目链接: https://cn.vjudge.net/problem/UVA-652
这道题由于多组数据发现各个(A*)好像不太行,于是就先一遍BFS扩展出所有状态同时记录路径,这一次没用哈希表用了康拓展开，然而不知道为何WA掉了。。。
代码:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#include <utility>
#include <iostream>
#define ll long long
#define ri register int
#define ull unsigned long long
using namespace std;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;return ;
}
const int maxn=5;
const int inf=0x7fffffff;
const int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
const char ch[4]={'u','l','r','d'};
const int fac[10]={1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int sta[maxn][maxn];
ll st,goal;
struct Sta{
ll a;int v;
Sta(){;}
Sta(ll _a,int _v){a=_a,v=_v;}
};
int bx,by;//0位置
int num[10],len[500005];
char path[500005][75];
inline ll turn_num(){
ll ans=0;
for(ri i=1;i<=3;i++){
for(ri j=1;j<=3;j++){
ans=ans*10+sta[i][j];
num[(i-1)*3+j]=sta[i][j];
}
}
return ans;
}
inline int cal_cantor(){
int sml=0,x=0;
for(ri i=1;i<=9;i++){
sml=0;
for(ri j=i+1;j<=9;j++){
if(num[j]<num[i])++sml;
}
x+=fac[9-i]*sml;
}
return x+1;
}
inline void turn_sta(ll p){
for(ri i=3;i>=1;i--){
for(ri j=3;j>=1;j--){
sta[i][j]=p%10;
p=p/10;
if(sta[i][j]==9)bx=i,by=j;
}
}
return ;
}
bool vis[500005];
inline void bfs(){
ll now,nxt;
int x,y,z,pre_val,val;
Sta tmp;
queue<Sta>q;
while(q.size())q.pop();//puts("wtf");
turn_sta(goal);
z=turn_num();
val=cal_cantor();
vis[val]=1;
q.push(Sta(goal,val));
while(q.size()){
tmp=q.front();q.pop();
now=tmp.a,pre_val=tmp.v;
turn_sta(now);
for(ri k=0;k<4;k++){
x=bx+dx[k],y=by+dy[k];
if(x>=1&&x<=3&&y>=1&&y<=3){
swap(sta[bx][by],sta[x][y]);
nxt=turn_num();
val=cal_cantor();
//printf("%d %d %lld %d %d
",x,y,nxt,val,pre_val);
if(!vis[val]){
vis[val]=1;
for(ri i=1;i<=len[pre_val];i++){
path[val][i]=path[pre_val][i];
}
len[val]=len[pre_val];
path[val][++len[val]]=ch[k];
q.push(Sta(nxt,val));
}
swap(sta[bx][by],sta[x][y]);
}
}
}
return ;
}
int main(){
/*234150768*/
/*123456780*/
/*
2
2 3 4 1 5 x 7 6 8
2 3 4 1 5 x 7 6 8
*/
std::ios_base::sync_with_stdio(0);
cin.tie(NULL);
int t,val;
char kkk;
read(t);
goal=123456789;
memset(vis,0,sizeof(vis));
bfs();
while(t--){
st=0;
for(ri i=1;i<=9;i++){
cin>>kkk;//scanf("%s",x);
if(kkk=='x')st=st*10,num[i]=9;
else st=st*10+kkk-'0',num[i]=kkk-'0';
}
val=cal_cantor();
//printf("%d %d
",val,len[val]);
if(!vis[val]){
puts("unsolvable");
}
else{
for(ri i=len[val];i>=1;i--)putchar(path[val][i]);
puts("");
}
if(t)puts("");
}
return 0;
}