洛谷 P1379 八数码难题 A* 题解
刚做完一道模板A*，看到这题我直接小脑萎缩了...
阿米诺斯！这怎么用A*？！——刚开题的我 beeeeeeeeee like
甚至比模板简单（这是绿的...）
其实会是会但是纸张的是这玩意我不会搞估价函数我草！
然后突然想到能不能把这个状态下有多少个数字不在目标位置作为估价函数？
我喜欢 \(IDA*\)，有兴趣的读者可以写普通的 \(A*\)。
毕竟 \(IDA*\) 好写啊。
结果调了很久，wssb。
本题代码
#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
i128 f=1;
x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}
void writing(i128 x)
{
if(x>=10)writing(x/10);
putchar(x%10+'0');
}
void write(i128 x)
{
if(x<0)
{
cout<<'-';
x=-x;
}
writing(x);
}
char ch[20];
LL en[4][4]=
{
{0,0,0,0},
{0,1,2,3},
{0,8,0,4},
{0,7,6,5}
};
LL a[10][10],sd;
bool don;
LL dx[]={0,1,-1,0};
LL dy[]={1,0,0,-1};
bool che()
{
rep(i,1,3,1)
{
rep(j,1,3,1)
{
if(en[i][j]!=a[i][j])return 0;
}
}
return 1;
}
bool gg(LL sp)
{
LL sum=0;
rep(i,1,3,1)
{
rep(j,1,3,1)
{
if(en[i][j]!=a[i][j])
{
sum++;
if(sum+sp>sd)
{
return 0;
}
}
}
}
return 1;
}
void idastar(LL sp,LL x,LL y,LL bef)
{
if(sp==sd)
{
if(che())don=1;
return;
}
repn(i,0,4,1)
{
LL nx=x+dx[i],ny=y+dy[i];
if(nx<1||nx>3||ny<1||ny>3||bef+i==3)continue;
swap(a[x][y],a[nx][ny]);
if(gg(sp)&&!don)
{
idastar(sp+1,nx,ny,i);
}
swap(a[x][y],a[nx][ny]);
}
}
int main()
{
LL x,y;
cin>>ch;
repn(i,0,9,1)
{
a[i/3+1][i%3+1]=ch[i]-'0';
if(ch[i]-'0'==0)
{
x=i/3+1;
y=i%3+1;
}
}
if(che())
{
cout<<0<<endl;
}
else
{
while(1)
{
sd++;
idastar(0,x,y,-1);
if(don)
{
cout<<sd<<endl;
break;
}
}
}
return 0;
}