#define FOR(i,n) for(int i=0; i<n; ++i)
#define GET(type,name) type name; std::cin >> name;


#include <iostream>
#include <vector>
#include <utility>
#include <utility>
#include <algorithm>
#include <queue>
#include <numeric>
#include <unordered_map>


    typedef std::vector<std::vector<int>> State;
    const int N = 3;

    State int_to_state(int c){
      std::vector<std::vector<int>> state(N, std::vector<int>(N));
      FOR(i, N) {
        FOR(j, N) {
          int r = c%10;
          c = c/10;
          state[i][j] = r;
        }
      }
      return state;
    }
    int state_to_int(State state) {
      int c = 0;
      int p = 1;
      FOR(i, N) {
        FOR(j, N) {
          c += state[i][j] * p;
          p *= 10;
        }
      }
      return c;
    }


    void show(std::vector<std::vector<int>> state){
      FOR(i, N) {
        FOR(j, N) {
          std::cout << state[i][j] << " ";
        }
        std::cout << std::endl;
      }
    }

    bool is_solved(const State& state) {
      int N = state.size();

      FOR(i, N) {
        FOR(j, N) {
          if(state[i][j] != (1 + 3*i + j)) return false;
        }
      }
      return true;
    }

    std::vector<State> next_states_of(State state){
      std::vector<State> res;
      FOR(i,N){
        FOR(j,N){
          if(state[i][j] == 9){
            State ns;
            if(i<N-1){
              ns = state;
              std::swap(ns[i][j], ns[i+1][j]);
              res.push_back(ns);
            }
            if(j<N-1){
              ns = state;
              std::swap(ns[i][j], ns[i][j+1]);
              res.push_back(ns);
            }
            if(i>0){
              ns = state;
              std::swap(ns[i][j], ns[i-1][j]);
              res.push_back(ns);
            }
            if(j>0){
              ns = state;
              std::swap(ns[i][j], ns[i][j-1]);
              res.push_back(ns);
            }
            return res;
          }
        }
      }

//      auto ns = state; std::swap(ns[0][0], ns[0][1]); res.push_back(ns);
//      ns = state; std::swap(ns[0][1], ns[0][2]); res.push_back(ns);
//      ns = state; std::swap(ns[1][0], ns[1][1]); res.push_back(ns);
//      ns = state; std::swap(ns[1][1], ns[1][2]); res.push_back(ns);
//      ns = state; std::swap(ns[2][0], ns[2][1]); res.push_back(ns);
//      ns = state; std::swap(ns[2][1], ns[2][2]); res.push_back(ns);
//      ns = state; std::swap(ns[0][0], ns[1][0]); res.push_back(ns);
//      ns = state; std::swap(ns[1][0], ns[2][0]); res.push_back(ns);
//      ns = state; std::swap(ns[0][1], ns[1][1]); res.push_back(ns);
//      ns = state; std::swap(ns[1][1], ns[2][1]); res.push_back(ns);
//      ns = state; std::swap(ns[0][2], ns[1][2]); res.push_back(ns);
//      ns = state; std::swap(ns[1][2], ns[2][2]); res.push_back(ns);
//      std::cout << res.size() <<std::endl;

    }


    int solve_puzzle(State state){

      std::priority_queue<
        std::pair<int, int>,
        std::vector<std::pair<int, int>>,
        std::greater<std::pair<int, int>>
      > q;
      std::unordered_map<int, int> h;

      q.push(std::make_pair(0, state_to_int(state)));

      for(;not q.empty();){
        auto d_s = q.top(); q.pop();
        int d = d_s.first;
        int st_int = d_s.second;
        State state = int_to_state(d_s.second);
//        show(state);

        if(st_int == 987654321){
//          std::cout << "z"<< std::endl;
          return d;
        }

        if(h.find(st_int) == h.end()){
          h[st_int] = d;
          std::vector<State> next_states = next_states_of(state);
          for(auto ns : next_states){
            q.push(std::make_pair(d+1, state_to_int(ns)));
          }
        }
      }
      return -1;
    }

    int main(){
      const int N = 3;
      std::vector<std::vector<int>> state(N, std::vector<int>(N));

      FOR(i, N){
        FOR(j, N){
          GET(int, x);
          if(x==0) x=9;
          state[i][j] = x;
        }
      }
//      show(state);
//      int c = state_to_int(state);
//      std::cout << c << std::endl;
//      std::cout << "?" <<std::endl;
//      State s2 = int_to_state(c);
//      std::cout << "!" <<std::endl;
//
//      show(s2);
//      int min_steps = rec_min_steps_
      std::cout << solve_puzzle(state) << std::endl;
      return 0;
    }

Measured memory_bytes: 11004