cses #game

/**
 * 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>;
 
const int B=3;
const int MASK=0x7;
 
/*
int doSwap(int va, int i1, int i2) {
    int v1=(va&(MASK<<(i1*B)))>>(i1*B);
    int v2=(va&(MASK<<(i2*B)))>>(i2*B);
 
    va= (va & ~(MASK<<(i1*B))) | (MASK<<(i2*B));
    va= (va & ~(MASK<<(i2*B))) | (MASK<<(i1*B));
}
 
int toInt(const string& s) {
    int ans=0;
    for(int i=0; i<8; i++)  {
        ans<<=B;
        ans+=(s[i]-'2');
    }
    return ans;
}
 
string toString(int va) {
    string ans(8,' ');
    for(int i=0; i<8; i++)  {
        ans[i]='2'+(va&MASK);
        va>>=B;
    }
}
*/
 
/* 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 }
};
 
const unordered_map<string,int> calcDp() {
    unordered_map<string,int> ldp;
    string a="123456789";
    ldp[a]=1;
    queue<string> q;
    q.push(a);
 
    while(q.size()) {
        string cur=q.front();
        q.pop();
        int dpcur=ldp[cur];
        string next=cur;
        for(pii p : sw) {
            char tmp=next[p.first];
            next[p.first]=next[p.second];
            next[p.second]=tmp;
 
            int dpnext=ldp[next];
            if(dpnext==0) {
                ldp[next]=dpcur+1;
                q.push(next);
            }
 
            next[p.second]=next[p.first];
            next[p.first]=tmp;
        }
    }
    return ldp;
}
 
const unordered_map<string,int> dp=calcDp();
 
/* 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() {
    string a(9,' ');
    for(int i=0; i<9; i++)
        cin>>a[i];
 
    if(dp.find(a)!=dp.end()) {
        int ans=dp.find(a)->second-1;
        cout<<ans<<endl;
    } else
        assert(false);
}
 
signed main() {
    solve();
}