剛做完一道模板A*，看到這題我直接小腦萎縮了... 阿米諾斯！這怎麼用A*？！——剛開題的我 beeeeeeeeee like 甚至比模板簡單（這是綠的...） 其實會是會但是紙張的是這玩意我不會搞估價函數我草！ 然後突然想到能不能把這個狀態下有多少個數字不在目標位置作為估價函數？ 我喜歡 \(ID ...
剛做完一道模板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;
}
