Shared code

/**
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */

#include <bits/stdc++.h>
using namespace std;

const bool ready = []() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(12);
    return true;
}();

const double PI = acos(-1);
using ll= long long;
#define int ll
#define all(v) (v).begin(), (v).end()
#define fori(n) for(int i=0; i<int(n); i++)

#define cini(i) int i; cin>>i;
#define cins(s) string s; cin>>s;
#define cind(d) double d; cin>>d;
#define cinai(a,n) vi a(n); fori(n) { cin>>a[i]; }
#define cinas(s,n) vs s(n); fori(n) { cin>>s[i]; }
#define cinad(a,n) vd a(n); fori(n) { cin>>a[i]; }

using pii= pair<int, int>;
using pdd= pair<double, double>;
using vd= vector<double>;
using vb= vector<bool>;
using vi= vector<int>;
using vvi= vector<vi>;
using vs= vector<string>;

/* the possible swaps */
constexpr pii sw[]= {
    { 0,3 },
    { 1,4 },
    { 2,5 },
    { 3,6 },
    { 4,7 },
    { 5,8 },
    { 0,1 },
    { 1,2 },
    { 3,4 },
    { 4,5 },
    { 6,7 },
    { 7,8 }
};

char dp[9][9][9][9][9][9][9][9][9];

vector<signed> Q(9);

bool calcDp() {
    vector<signed> a={0,1,2,3,4,5,6,7,8};
    dp[0][1][2][3][4][5][6][7][8]=(char)1;
    queue<vector<signed>> q;
    q.push(a);

    if(a==Q) {
        cout<<0<<endl;
        return true;
    }

    while(q.size()) {
        vector<signed> b=q.front();
        q.pop();

        const char dpcur=dp[b[0]][b[1]][b[2]][b[3]][b[4]][b[5]][b[6]][b[7]][b[8]];

        for(pii p : sw) {
            swap(b[p.first], b[p.second]);
            signed dpnext=dp[b[0]][b[1]][b[2]][b[3]][b[4]][b[5]][b[6]][b[7]][b[8]];
            if(dpnext==0) {
                dp[b[0]][b[1]][b[2]][b[3]][b[4]][b[5]][b[6]][b[7]][b[8]]=dpcur+1;
                q.push(b);
                if(b==Q) {
                    cout<<(int)dpcur<<endl;
                    return true;
                }
            }
            swap(b[p.first], b[p.second]);
        }
    }
    assert(false);
}


/* swap _adjacent_ fields
 * There are 12 different moves
 * possible.
 * Note that there are only 9! different
 * states.
 * Ie it is simple BFS.
 * ****************
 * Unfortunatly it turns out that this is to slow, ~3000ms
 * We would need to find a way to map the 9! permutations to the first 9! integers,
 * then we could use BFS in a quicker way.
 *
 * *****************
 * Other strategy:
 * move the 1 in place fastest possible, then permute only the other positions.
 * ...
 * And it turns out then we have to put 8 different numbers into 8 positions.
 * Since we can place 8 different numbers into 3 bits this is only 24 bits,
 * ie fits in array of size 16M.
 * So we do not need a map for dp, we can use vector instead.
 * ... turns out there are some wrong ones :/
 * 4 2 7
 * 6 8 3
 * 1 5 9
 * We cannot swap the 1 and 6 in first place. It is better to first
 * move the 7 to the place of the 6...
 * *****************
 * Ok. Lets calculate the distance to all permutations per compiletime.
 * Then output solution in O(1)
 * ...turns out this is difficult :/
 **/
void solve() {
    vi a(9);
    for(int i=0; i<9; i++) {
        cin>>Q[i];
        Q[i]--;
    }

    calcDp();
    //cout<<dp[a[0]][a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]]-1<<endl;
}

signed main() {
    solve();
}

// FIRST THINK, THEN CODE
// DO NOT JUMP BETWEEN PROBLEMS