#include<iostream>
#include<map> //I'm sorry to use map
#include<algorithm>
using namespace std;

struct Puz{
  int board[3][3];
  int zx, zy; //coodinate of zero
  int cnt;

  bool operator < (const Puz &p)const{
    for(int i = 0;i < 3;i++){
      for(int j = 0;j < 3;j++){
        if(board[i][j] == p.board[i][j]) continue;
        return board[i][j] > p.board[i][j];
      }
    }
    return false;
  }

  bool operator == (const Puz &p)const{
    for(int i = 0;i < 3;i++){
      for(int j = 0;j < 3;j++){
        if(board[i][j] != p.board[i][j]) return false;
      }
    }
    return true;
  }
};



int d[5] = {0, -1, 0, 1, 0}; //direction
Puz g = {{{1, 2, 3}, {4, 5, 6}, {7, 8, 0}}}; //goal
map<Puz, int> mem; //memory

//queue
int head, tail;
Puz Q[30000];

void enqueue(Puz x){

  Q[tail] = x;

  if(tail + 1 == 30000) tail = 0;
  else tail++;
}

Puz dequeue(){

  Puz x = Q[head];

  if(head + 1 == 30000) head = 0;
  else head++;

  return x;
}

//solve
int bfs(Puz s){

  enqueue(s);
  mem[s] = 1;

  while(head != tail){
    Puz p = dequeue(), q;

    if(p == g) return p.cnt;

    for(int i = 0;i < 4;i++){
      int x = p.zx + d[i], y = p.zy + d[i + 1];

      if(0 <= x && x < 3 && 0 <= y && y < 3){
        q = p;
        swap(q.board[q.zy][q.zx], q.board[y][x]);
        q.zy = y;
        q.zx = x;
        q.cnt++;
        if(!mem[q]++) enqueue(q); //memorizing
      }
    }
  }

  return 0;
}

int main(){

  Puz s;

  //input
  for(int i = 0;i < 3;i++){
    for(int j = 0;j < 3;j++){
      cin >> s.board[i][j];
      if(s.board[i][j] == 0){
        s.zy = i;
        s.zx = j;
      }
    }
  }
  s.cnt = 0;

  //output
  cout << bfs(s) << endl;

  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

The goal of the 8 puzzle problem is to complete pieces on $3 \times 3$ cells where one of the cells is empty space.

In this problem, the space is represented by 0 and pieces are represented by integers from 1 to 8 as shown below.


1 3 0
4 2 5
7 8 6


You can move a piece toward the empty space at one step. Your goal is to make the pieces the following configuration in the shortest move (fewest steps).


1 2 3
4 5 6
7 8 0


Write a program which reads an initial state of the puzzle and prints the fewest steps to solve the puzzle.

Constraints

* There is a solution.

Input

The $3 \times 3$ integers denoting the pieces or space are given.

Output

Print the fewest steps in a line.

Example

Input

1 3 0
4 2 5
7 8 6


Output

4

### Response

```cpp
#include<iostream>
#include<map> //I'm sorry to use map
#include<algorithm>
using namespace std;

struct Puz{
  int board[3][3];
  int zx, zy; //coodinate of zero
  int cnt;

  bool operator < (const Puz &p)const{
    for(int i = 0;i < 3;i++){
      for(int j = 0;j < 3;j++){
        if(board[i][j] == p.board[i][j]) continue;
        return board[i][j] > p.board[i][j];
      }
    }
    return false;
  }

  bool operator == (const Puz &p)const{
    for(int i = 0;i < 3;i++){
      for(int j = 0;j < 3;j++){
        if(board[i][j] != p.board[i][j]) return false;
      }
    }
    return true;
  }
};



int d[5] = {0, -1, 0, 1, 0}; //direction
Puz g = {{{1, 2, 3}, {4, 5, 6}, {7, 8, 0}}}; //goal
map<Puz, int> mem; //memory

//queue
int head, tail;
Puz Q[30000];

void enqueue(Puz x){

  Q[tail] = x;

  if(tail + 1 == 30000) tail = 0;
  else tail++;
}

Puz dequeue(){

  Puz x = Q[head];

  if(head + 1 == 30000) head = 0;
  else head++;

  return x;
}

//solve
int bfs(Puz s){

  enqueue(s);
  mem[s] = 1;

  while(head != tail){
    Puz p = dequeue(), q;

    if(p == g) return p.cnt;

    for(int i = 0;i < 4;i++){
      int x = p.zx + d[i], y = p.zy + d[i + 1];

      if(0 <= x && x < 3 && 0 <= y && y < 3){
        q = p;
        swap(q.board[q.zy][q.zx], q.board[y][x]);
        q.zy = y;
        q.zx = x;
        q.cnt++;
        if(!mem[q]++) enqueue(q); //memorizing
      }
    }
  }

  return 0;
}

int main(){

  Puz s;

  //input
  for(int i = 0;i < 3;i++){
    for(int j = 0;j < 3;j++){
      cin >> s.board[i][j];
      if(s.board[i][j] == 0){
        s.zy = i;
        s.zx = j;
      }
    }
  }
  s.cnt = 0;

  //output
  cout << bfs(s) << endl;

  return 0;
}

```