本地可过样例 + 两组数据，但上洛谷就 RE.

经过测试，把 A* 里的 push(v) 注释掉就不会 RE 了. 开始以为是 pq 的元素太多炸掉了，但限定层数之后还是 RE，是在看不出来了求大佬帮忙康康.

/*
#########################################
#                                       #
# @Author: CreeperOI                    #
# @Date: 2023-10-30 15:54:16            #
#                                       #
#########################################
*/
#include <bits/stdc++.h>
#define debug
using namespace std;

// const int mod = 1e9 + 7;

// ------------------------- templates above -------------------------

// int const N = 1e5 + 10;

string n, ans = "123804765";

struct node{
    string cur;
    int step, v;
    bool operator < (const node &a) const {
        return v > a.v;
    };
};

int h(string cur, int step){
    int tot = 0, ze = 0;
    string tmp[3];
    string tans[] = {"123", "804", "765"};
    tmp[0] = cur[0] + cur[1] + cur[2];
    tmp[1] = cur[3] + cur[4] + cur[5];
    tmp[2] = cur[6] + cur[7] + cur[8];
    if (tmp[1][1] == 0) ze = 1;
    for (int i = 0;i <= 2;++i){
        for (int j = 0;j <= 2;++j){
            int flag = 0;
            for (int k = 0;k <= 2;++k){
                for (int l = 0;l <= 2;++l){
                    if (tmp[i][j] == tans[k][l]){
                        tot += abs(i - k) + abs(j - l);
                        flag = 1;
                        break;
                    }
                }
                if (flag == 1) break;
            }
        }
    }
    tot *= 3;
    tot += step + ze;
    return tot;
}

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

map <string, int> vis;
map <string, int> dis;

void mian(){
    cin >> n;
    priority_queue <node> q;
    q.push((node){n, 0, h(n, 0)});
    vis[n] = 1;
    dis[n] = 0;
    while (!q.empty()){
        node u = q.top();
        q.pop();
        if (u.cur == ans){
            cout << u.step << endl;
            return;
        }
        int x0, y0;
        for (int i = 0;i <= 8;++i)
            if (u.cur[i] == '0') x0 = i / 3, y0 = i % 3;
        for (int i = 0;i <= 3;++i){
            int ux = x0 + dx[i], uy = y0 + dy[i];
            node v = (node){u.cur, u.step + 1, 0};
            swap(v.cur[x0 * 3 + y0],v.cur[ux * 3 + uy]);
            v.v = h(v.cur, v.step);
            if (ux >= 0 && ux <= 2 && uy >= 0 && uy <= 2)
                if (vis[v.cur] == 0 || (dis[u.cur] + 1 < dis[v.cur])){
                    vis[v.cur] = 1;
                    dis[v.cur] = dis[u.cur] + 1;
                    q.push(v);
                }
        }
    }
}
int main() {
    int T = 1;
    while(T--) mian();
    return 0;
}