在 P1379 里面 wa 呀 wa 呀 wa……

https://www.luogu.com.cn/record/113358610

https://www.luogu.com.cn/record/113280695

算法：A*

代码：

#include<bits/stdc++.h>
using namespace std;
const string target="123804765";
string s;
int d[]={3,-3,1,-1};
struct Node
{
	string str;
	int zeropos;
	int step;
	int uss;
};
bool operator >(Node A,Node B)
{
	return A.uss>B.uss;
}
priority_queue<Node,vector<Node>,greater<Node> > que;
map<string,int> flag;
int rmb(string x)//估价
{
	int res=0;
	for(int i=0;i<=9;i++)res+=(x[i]!=target[i]);
	return res;
}
int bfs()
{
	flag[s]=1;
	int k;
	for(k=0;k<9;k++)
	{
		if(s[k]=='0')break;
	}
	que.push((Node){s,k,0,rmb(s)});
	while(!que.empty())
	{
		Node m=que.top();
		que.pop();
		string mstr=m.str;
		int mzeropos=m.zeropos;
		int mstep=m.step;
		if(mstr==target)return mstep;
		for(int i=0;i<4;i++)
		{
			if(i==2&&mzeropos%3==2)continue;
			if(i==3&&mzeropos%3==0)continue;
			int nowzeropos=mzeropos+d[i];
			if(nowzeropos<0||nowzeropos>=9)continue;
			string nowstr=mstr;
			swap(nowstr[nowzeropos],nowstr[mzeropos]);
			if(flag[nowstr])continue;
			flag[nowstr]=1;
			que.push((Node){nowstr,nowzeropos,mstep+1,mstep+1+rmb(nowstr)});
		}
	}
}
int main()
{
	cin>>s;
	int ans=bfs();
	cout<<ans;
	return 0;
}

大佬求调 QwQ