洛谷 P1379 八数码难题 A* 题解-Toy模板网

这篇具有很好参考价值的文章主要介绍了洛谷 P1379 八数码难题 A* 题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

刚做完一道模板A*，看到这题我直接小脑萎缩了...

阿米诺斯！这怎么用A*？！——刚开题的我 beeeeeeeeee like

甚至比模板简单（这是绿的...）

其实会是会但是纸张的是这玩意我不会搞估价函数我草！

然后突然想到能不能把这个状态下有多少个数字不在目标位置作为估价函数？

我喜欢 \(IDA*\)，有兴趣的读者可以写普通的 \(A*\)。

毕竟 \(IDA*\) 好写啊。

结果调了很久，wssb。文章来源地址https://www.toymoban.com/news/detail-842386.html

本题代码

#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;
}

到了这里，关于洛谷 P1379 八数码难题 A* 题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！