RT，下面这份代码使用了 A* 算法。

#include <bits/stdc++.h>

#define FstIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pb push_back
#define mem(a, v) memset(a, v, sizeof a)
#define pii pair<ll, ll>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
 
const ll N = 12 + 5, M = 80 + 5; 
const ll mod = 1e9 + 7, mod2 = 998244353;
const ld eps = 1e-6;

string s;

ll A[N][N], Ans[N][N] = {{1, 2, 3}, {8, 0, 4}, {7, 6, 5}};

bool chkfinal()
{
	for (ll i = 0; i < 3; ++ i ) 
		for (ll j = 0; j < 3; ++ j )
			if (A[i][j] != Ans[i][j]) return false;
	return true;
}

ll func(ll stp, ll k)
{
	ll c = 0;
	for (ll i = 0; i < 3; ++ i )
	{
		for (ll j = 0; j < 3; ++ j )
		{
			if (A[i][j] != Ans[i][j]) 
			{
				if ((++ c) + stp > k) return false;
			}
		}	
	}
		
	return true;
}

ll dx[] = {0, -1, 1, 0}, dy[] = {1, 0, 0, -1};

void A_star(ll stp, ll x, ll y, ll Rge, ll lst)
{
	if (stp == Rge)
	{
		if (chkfinal())
		{
			cout << stp << '\n';
			exit(0);
		}
		return ;
	}
	for (ll i = 0; i < 4; ++ i )
	{
		ll nx = x + dx[i], 
		   ny = y + dy[i];
		if (~nx && ~ny && nx < 3 && ny < 3 && lst + i != 3)
		{
			swap(A[x][y], A[nx][ny]); 
			if (func(stp, Rge) ) A_star(stp + 1, nx, ny, Rge, i);
			swap(A[x][y], A[nx][ny]); 
		} 
	}
}

signed main()
{
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);

	FstIO; 
	
	cin >> s; 
	for (ll i = 0; i < s.size(); ++ i ) 
	{
		A[i / 3][i % 3] = s[i] - '0';
	}
	if (chkfinal()) { cout << "0\n"; return 0; }
	
	ll c = 1, startx, starty;
	for (ll i = 0; i < 3; ++ i )
		for (ll j = 0; j < 3; ++ j )
			if (!A[i][j]) startx = i, starty = j;
			
	while (c) 
	{
		A_star(0, startx, starty, c, -114);
		++ c;
	}
	
	return 0;
	
	cout.flush();
}

为什么在 A* 里调用估价函数 func 时，参数为 stp 而不是 stp + 1。如果使用后者会 TLE，不是很理解