#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <vector>

using namespace std;

#define SIDE 3
#define N 9

typedef struct board {
  int state[N];
  int zero_pos;
  vector<int> path;

  bool operator < (const board &t) const {
    for (int i = 0; i < N; i++) {
      if (state[i] == t.state[i]) continue;
      else if (state[i] < t.state[i]) return true;
      else return false;
    }
    return false;
  }
} Board;

int BOARD[N] = { -1 };
int DX[4] = { 0, 1, 0, -1 };
int DY[4] = { 1, 0, -1, 0 };

bool is_goal(Board b) {
  for (int i = 0; i < N-1; i ++)
    if (b.state[i] != i+1) return false;

  return true;
}

void solve(Board b) {
  map<Board, bool> visited;
  queue<Board> q;
  q.push(b);

  while (!q.empty()) {
    Board cur_b = q.front(); q.pop();
    visited[cur_b] = true;

    if (is_goal(cur_b)) {
      cout << cur_b.path.size() << endl;
      return;
    }

    for (int i = 0; i < 4; i ++) {
      Board new_b = cur_b;
      int new_x = (cur_b.zero_pos / SIDE) + DX[i];
      int new_y = (cur_b.zero_pos % SIDE) + DY[i];

      if (new_x < 0 || new_x > 2 || new_y < 0 || new_y > 2) continue;

      new_b.zero_pos = new_x * SIDE + new_y;
      swap(new_b.state[new_b.zero_pos], new_b.state[cur_b.zero_pos]);

      if (visited[new_b]) continue;

      new_b.path.push_back(new_b.zero_pos);
      q.push(new_b);
    }
  }
}

int main() {
  Board b;

  for (int i = 0; i < N; i++) {
    cin >> b.state[i];
    if (b.state[i] == 0) b.zero_pos = i;
  }

  solve(b);
}
### Prompt

Develop a solution in CPP 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 <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <vector>

using namespace std;

#define SIDE 3
#define N 9

typedef struct board {
  int state[N];
  int zero_pos;
  vector<int> path;

  bool operator < (const board &t) const {
    for (int i = 0; i < N; i++) {
      if (state[i] == t.state[i]) continue;
      else if (state[i] < t.state[i]) return true;
      else return false;
    }
    return false;
  }
} Board;

int BOARD[N] = { -1 };
int DX[4] = { 0, 1, 0, -1 };
int DY[4] = { 1, 0, -1, 0 };

bool is_goal(Board b) {
  for (int i = 0; i < N-1; i ++)
    if (b.state[i] != i+1) return false;

  return true;
}

void solve(Board b) {
  map<Board, bool> visited;
  queue<Board> q;
  q.push(b);

  while (!q.empty()) {
    Board cur_b = q.front(); q.pop();
    visited[cur_b] = true;

    if (is_goal(cur_b)) {
      cout << cur_b.path.size() << endl;
      return;
    }

    for (int i = 0; i < 4; i ++) {
      Board new_b = cur_b;
      int new_x = (cur_b.zero_pos / SIDE) + DX[i];
      int new_y = (cur_b.zero_pos % SIDE) + DY[i];

      if (new_x < 0 || new_x > 2 || new_y < 0 || new_y > 2) continue;

      new_b.zero_pos = new_x * SIDE + new_y;
      swap(new_b.state[new_b.zero_pos], new_b.state[cur_b.zero_pos]);

      if (visited[new_b]) continue;

      new_b.path.push_back(new_b.zero_pos);
      q.push(new_b);
    }
  }
}

int main() {
  Board b;

  for (int i = 0; i < N; i++) {
    cin >> b.state[i];
    if (b.state[i] == 0) b.zero_pos = i;
  }

  solve(b);
}
```