#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <stdlib.h>
#include <limits.h>
#include <unordered_map>
#include <string>
#include <map>
#include <sstream>
#include <cstdlib> 
using namespace std;

#define INF     INT_MAX
#define SIZE  9
#define WIDTH 3

#define LEFT  0
#define RIGHT 1
#define UP    2
#define DOWN  3

typedef struct{
  int            dist;        // accumulated distance fromt start board 
  int            evaluation;
  bool           visited;     // default: false
} v_t;

map< string, v_t >  Node; // Key: cell hash, Value: node
void assert(vector<int> v);

bool Move[SIZE][4];
void initMove(){
  // Can Move Right?
  Move[0][RIGHT]=Move[1][RIGHT]=Move[3][RIGHT]=Move[4][RIGHT]=Move[6][RIGHT]=Move[7][RIGHT]=true;
  Move[2][RIGHT]=Move[5][RIGHT]=Move[8][RIGHT]=false;
  // Can Move Left?
  Move[1][LEFT]=Move[2][LEFT]=Move[4][LEFT]=Move[5][LEFT]=Move[7][LEFT]=Move[8][LEFT]=true;
  Move[0][LEFT]=Move[3][LEFT]=Move[6][LEFT]=false;
  // Can Move Up?
  Move[3][UP]=Move[4][UP]=Move[5][UP]=Move[6][UP]=Move[7][UP]=Move[8][UP]=true;
  Move[0][UP]=Move[1][UP]=Move[2][UP]=false;
  // Can Move Down?
  Move[0][DOWN]=Move[1][DOWN]=Move[2][DOWN]=Move[3][DOWN]=Move[4][DOWN]=Move[5][DOWN]=true;
  Move[6][DOWN]=Move[7][DOWN]=Move[8][DOWN]=false;
}

multimap< int, string > Q;   // Key: dist + evaluation , Value: cell hash
string hashkey(vector<int> cell){
  string hash;
  for(const auto& e: cell){
    hash += to_string(e) + ",";
  }
  return hash;
}

vector<string> split(const string &str, char sep)
{
  vector<string> v;
  stringstream ss(str);
  string buffer;
  while( getline(ss, buffer, sep) ) {
      v.push_back(buffer);
  }
  return v;
}
vector<int> dehash(string hash){
  vector<int> cell;
  vector<string> board = split(hash, ',');
  for(const auto& e : board){
    cell.push_back(stoi(e));
  }
  return cell;
}

int estimateH(vector<int> cell){
  int hr = 0; // heuristic
  for(int i = 0 ; i < SIZE ; i++){
    if(cell[i] == 0){
      cell[i] = SIZE;
    }
    hr += abs( (cell[i]-1)%WIDTH - i%WIDTH );
    hr += abs( (cell[i]-1)/WIDTH - i/WIDTH );
  }
	return hr;
}

vector<int> updateGQ(vector<int> curCell,int space, int dir){
  const string curHash = hashkey(curCell);
  vector<int> nextCell(curCell);
  int moveto = space + dir; // move to = space(0) + direction
  nextCell[space] = nextCell[moveto];
  nextCell[moveto] = 0;
  const string nextHash = hashkey(nextCell); 
  if( !Node[nextHash].visited ){
    Node[nextHash].visited = true;
  	Node[nextHash].dist = Node[curHash].dist + 1;
   	Node[nextHash].evaluation = estimateH(nextCell);
    int dist_ev = 1 + Node[curHash].dist + Node[curHash].evaluation;
		Q.insert(make_pair(dist_ev, nextHash));
  }
  return nextCell;
}

void move(vector<int> curCell){
  for(int i = 0 ; i < SIZE ; i++ ){
    vector<int> resultCell;
    if(curCell[i] == 0){
      if(Move[i][LEFT]){
        resultCell = updateGQ(curCell, i, -1); 
      }
      if(Move[i][RIGHT]){
        resultCell = updateGQ(curCell, i, 1 ); 
      }
      if(Move[i][UP]){
        resultCell = updateGQ(curCell, i, -3); 
      }
      if(Move[i][DOWN]){
        resultCell = updateGQ(curCell, i, 3); 
      }
    }
  }
  return;
}

void assert(vector<int> v){ // for debug
  int i = 0;
	for(auto itr = v.begin() ; itr != v.end(); ++itr){
    fprintf(stderr, "%d "  ,*itr);
    i++;
    if(i==3){
      i = 0;
      fprintf(stderr, "\n");
    }
  }
}

int main(){ // Dijkstra P.254
  vector<int> cell(SIZE); // current cell
  const vector<int> goalCell = {1,2,3,4,5,6,7,8,0};
  const string goalHash = hashkey(goalCell);
  initMove();
 
  //  insert First node
  for(int i = 0 ; i < SIZE ; i++){
    int num;
    scanf("%d" ,&num);
    cell[i] = num;
  }
  v_t firstNode = {0, 0, true};
  Node[hashkey(cell)] = firstNode;
	Q.insert( make_pair(0, hashkey(cell)) );
  move(cell);
  auto itr = Q.begin();
  Q.erase(itr);

  while(!Q.empty()){
    if( Node[goalHash].visited ){
      break;
    }
    auto itr = Q.begin();
    string curHash = itr->second;
    Q.erase(itr);
    cell = dehash(curHash);
    move(cell);
  }

  printf("%d\n" ,Node[goalHash].dist );
  return 0;
}




Measured memory_bytes: 10912