#include<iostream>
#include<queue>
#include<unordered_set>
using namespace std;

const int D_x[4] = { 0,1,0,-1 };
const int D_y[4] = { 1,0,-1,0 };
const int ANS = 123456780;

void setNum(int puzzle[3][3],int n) {
	for (int i = 2; i >= 0; i--) {
		for (int j = 2; j >= 0; j--) {
			puzzle[i][j] = n % 10;
			n /= 10;
		}
	}
}

int getNum(int puzzle[3][3]) {
	int res = 0;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			res *= 10;
			res += puzzle[i][j];
		}
	}
	return res;
}

void find_0(int puzzle[3][3], int& x, int& y) {
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (puzzle[i][j] == 0) {
				x = j;
				y = i;
				return;
			}
		}
	}
}

int solve(int puzzle[3][3]) {
	queue<int> q;
	unordered_set<int> table;
	int cnt = 1;

	q.push(getNum(puzzle));
	if (q.front() == ANS)return 0;
	while (true) {
		int s = q.size();

		for (int i = 0; i < s; i++) {
			int x, y;
			setNum(puzzle, q.front());
			find_0(puzzle, x, y);

			for (int j = 0; j < 4; j++) {
				int X = x + D_x[j];
				int Y = y + D_y[j];
				if (X < 0 || Y < 0 || X >= 3 || Y >= 3)continue;
				setNum(puzzle, q.front());
				swap(puzzle[y][x], puzzle[Y][X]);

				int n = getNum(puzzle);
				if (n == ANS) {
					return cnt;
				}
				if (table.count(n) == 0) {
					table.insert(n);
					q.push(n);
				}
			}
			q.pop();
		}
		cnt++;
	}
}

int main() {
	int puzzle[3][3];

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> puzzle[i][j];
		}
	}

	cout << solve(puzzle) << endl;

	return 0;
}
### Prompt

Please formulate a Cpp solution to 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<queue>
#include<unordered_set>
using namespace std;

const int D_x[4] = { 0,1,0,-1 };
const int D_y[4] = { 1,0,-1,0 };
const int ANS = 123456780;

void setNum(int puzzle[3][3],int n) {
	for (int i = 2; i >= 0; i--) {
		for (int j = 2; j >= 0; j--) {
			puzzle[i][j] = n % 10;
			n /= 10;
		}
	}
}

int getNum(int puzzle[3][3]) {
	int res = 0;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			res *= 10;
			res += puzzle[i][j];
		}
	}
	return res;
}

void find_0(int puzzle[3][3], int& x, int& y) {
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (puzzle[i][j] == 0) {
				x = j;
				y = i;
				return;
			}
		}
	}
}

int solve(int puzzle[3][3]) {
	queue<int> q;
	unordered_set<int> table;
	int cnt = 1;

	q.push(getNum(puzzle));
	if (q.front() == ANS)return 0;
	while (true) {
		int s = q.size();

		for (int i = 0; i < s; i++) {
			int x, y;
			setNum(puzzle, q.front());
			find_0(puzzle, x, y);

			for (int j = 0; j < 4; j++) {
				int X = x + D_x[j];
				int Y = y + D_y[j];
				if (X < 0 || Y < 0 || X >= 3 || Y >= 3)continue;
				setNum(puzzle, q.front());
				swap(puzzle[y][x], puzzle[Y][X]);

				int n = getNum(puzzle);
				if (n == ANS) {
					return cnt;
				}
				if (table.count(n) == 0) {
					table.insert(n);
					q.push(n);
				}
			}
			q.pop();
		}
		cnt++;
	}
}

int main() {
	int puzzle[3][3];

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> puzzle[i][j];
		}
	}

	cout << solve(puzzle) << endl;

	return 0;
}
```