#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;

int d_x[4] = { -1,0,1,0 };
int d_y[4] = { 0,1,0,-1 };

int t[3][3];
int level=0;

int countpath() {
	int ret=0;
	int tmp;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (t[i][j] != 0) {
				tmp = t[i][j] - 1;
				ret += abs(tmp / 3 - i) + abs(tmp % 3 - j);
			}
		}
	}
	return ret;
}

bool check(int depth, int pre, int px, int py) {
	int w = countpath();
	if (w + depth > level) return false;
	if (w == 0)return true;
	int dx, dy;
	for (int i = 0; i < 4; i++) {
		if (abs(i - pre) != 2) {
			dx = px + d_x[i];
			dy = py + d_y[i];
			if (dx < 0 || dx == 3 || dy < 0 || dy == 3) continue;
			swap(t[dx][dy], t[px][py]);
			if (check(depth + 1, i, dx, dy)) return true;
			swap(t[dx][dy], t[px][py]);
		}
		
	}
	return false;
}

void solution(int px, int py) {
	for (level = 0;; level++) {
		if (check(0, 9, px, py)) {
			cout << level << endl;
			return;
		}
	}
}

int main() {
	int px, py;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> t[i][j];
			if (t[i][j] == 0) {
				px = i;
				py = j;
			}
		}
	}
	solution(px,py);
	return 0;
}
### Prompt

Create a solution in Cpp for the following problem:

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 <math.h>
#include <algorithm>
using namespace std;

int d_x[4] = { -1,0,1,0 };
int d_y[4] = { 0,1,0,-1 };

int t[3][3];
int level=0;

int countpath() {
	int ret=0;
	int tmp;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (t[i][j] != 0) {
				tmp = t[i][j] - 1;
				ret += abs(tmp / 3 - i) + abs(tmp % 3 - j);
			}
		}
	}
	return ret;
}

bool check(int depth, int pre, int px, int py) {
	int w = countpath();
	if (w + depth > level) return false;
	if (w == 0)return true;
	int dx, dy;
	for (int i = 0; i < 4; i++) {
		if (abs(i - pre) != 2) {
			dx = px + d_x[i];
			dy = py + d_y[i];
			if (dx < 0 || dx == 3 || dy < 0 || dy == 3) continue;
			swap(t[dx][dy], t[px][py]);
			if (check(depth + 1, i, dx, dy)) return true;
			swap(t[dx][dy], t[px][py]);
		}
		
	}
	return false;
}

void solution(int px, int py) {
	for (level = 0;; level++) {
		if (check(0, 9, px, py)) {
			cout << level << endl;
			return;
		}
	}
}

int main() {
	int px, py;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> t[i][j];
			if (t[i][j] == 0) {
				px = i;
				py = j;
			}
		}
	}
	solution(px,py);
	return 0;
}
```