文章目录


#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define FI first
#define SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl; 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
const int maxn = 4e6+10;
bool vis[maxn];
int  d[maxn];
int fac[11];
const int nn = 9;
int cal(int n){ // 康托展开
    int cnt = 0;
    int a[11];
    // cout<<n<<endl;
    for(int i = 1;i <= nn; ++i){
         a[nn-i+1] = n % 10;
         n /= 10; 
    }
    
    for(int i = 1;i <= nn; ++i){
        int sum = 0;
        for(int j = i+1;j <= nn; ++j)
            if(a[j] < a[i])
                sum++;
        cnt += sum*fac[nn-i];
    }
    return cnt+1;
}
int num(int *a){
    int cnt = 0;
    for(int i = 1;i <= nn; ++i)
        cnt = cnt*10+a[i];
    return cnt;
}
void toarray(int *a,int n){
    for(int i = 1;i <= nn; ++i)
        a[i] = n%10,n /= 10;
    reverse(a+1,a+nn+1);
}
int S,T;

queue<int> Q;
void Insert(int *b,int y){
    int tmp = num(b);
    int t = cal(tmp);
    if(!vis[t]){
        vis[t] = true;
         // cout<<tmp<<" "<<cal(tmp)<<endl; 
        d[t] = y+1;
        // cout<<d[t]<<endl;
        Q.push(tmp);
    }
}
char ar[11];
char br[11]= " 123804765";
int main(void)
{

   fac[0] = 1;
   for(int i = 1;i <= 10; ++i)   
        fac[i] = fac[i-1]*i;
   cin>>(ar+1);
   for(int i = 1,u;i <= nn; ++i){
       u = ar[i]-'0';
       S = S*10+u;
   }
   for(int i = 1,u;i <= nn; ++i){
        u = br[i]-'0';
        T = T*10+u;
   }
   Q.push(S);
   vis[cal(S)] = true;
   while(!Q.empty()){
     int  x = Q.front(); Q.pop();
     int  xx = cal(x);
     int  y = d[xx];
     int a[11],b[11];
     toarray(a,x);

    // for(int i = 1;i <= nn; ++i)
    // cout<<a[i]<<" ";
    // cout<<endl;
     int index = 0;
     for(int i = 1;i <= nn; ++i)
        if(a[i] == 0)
            index = i;
     // cout<<index<<endl;
     if(index % 3 != 0){
        memcpy(b,a,sizeof(a));
        swap(b[index],b[index+1]);
        Insert(b,y);
     }
     if(index % 3 != 1){
        memcpy(b,a,sizeof(a));
        swap(b[index],b[index-1]);
        Insert(b,y);
     }
     if(index > 3){
        memcpy(b,a,sizeof(a));
        swap(b[index],b[index-3]);
        Insert(b,y);
     }
     if(index <= 6){
        memcpy(b,a,sizeof(a));
        swap(b[index],b[index+3]);
        Insert(b,y);
     }
   }
   cout<<d[cal(T)]<<endl;




   return 0;
}