#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 10;

typedef struct Node{
	int a[maxn];
	int step;
}Node;

int arr[maxn],start[maxn];//start arr 分别是开始和目标状态 
int cnt;//记录map的值 
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
map<int,int>mp;

int bfs(){
	queue<Node>que;
	Node node;
	memcpy(node.a,start,sizeof(start));
	node.step = 0;
	que.push(node);
	while(!que.empty()){
		//for()...
		node = que.front();
		que.pop();
		int index;
		for(int i = 0; i<9; i++){
			if(node.a[i] == 0) index = i;
		}
		int r = index/3;
		int c = index%3;
		for(int i = 0; i<4; i++){
			int nr = r + dx[i];
			int nc = c + dy[i];
			if(0<=nr && nr<3 && 0<=nc && nc<3){
				Node node_new;
				int index_new = nr*3 + nc;
				int sum = 0;
				memcpy(node_new.a,node.a,sizeof(node.a));				
				swap(node_new.a[index],node_new.a[index_new]);
				for(int j = 0; j<9; j++){
					sum = sum*10 + node_new.a[j];
				}
				if(mp[sum] == 0){
					mp[sum] = cnt++;
					node_new.step = node.step+1;
					if(memcmp(arr,node_new.a,sizeof(arr)) == 0){
						return node_new.step;
					}
					que.push(node_new);
				}
			}
		}
		//if !vis[i] ...que.push
	}
}
int main()
{
	int sum1 = 0, cnt = 0, sum = 0;
	for(int i = 1; i<=8; i++){
		sum1 = sum1*10 + i;
		start[i-1] = i; 
	}
	sum1 = sum1*10;
	start[8] = 0;
	mp[sum1] = cnt++;
	for(int i = 0; i<9; i++){
		scanf("%d",&arr[i]);
		sum = sum*10 + arr[i];
	}
	if(sum == sum1) printf("0\n");
	else{
		printf("%d\n",bfs());
	}
	
	return 0;
}

### Prompt

Your task is to create 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<cstdio>
#include<cstring>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 10;

typedef struct Node{
	int a[maxn];
	int step;
}Node;

int arr[maxn],start[maxn];//start arr 分别是开始和目标状态 
int cnt;//记录map的值 
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
map<int,int>mp;

int bfs(){
	queue<Node>que;
	Node node;
	memcpy(node.a,start,sizeof(start));
	node.step = 0;
	que.push(node);
	while(!que.empty()){
		//for()...
		node = que.front();
		que.pop();
		int index;
		for(int i = 0; i<9; i++){
			if(node.a[i] == 0) index = i;
		}
		int r = index/3;
		int c = index%3;
		for(int i = 0; i<4; i++){
			int nr = r + dx[i];
			int nc = c + dy[i];
			if(0<=nr && nr<3 && 0<=nc && nc<3){
				Node node_new;
				int index_new = nr*3 + nc;
				int sum = 0;
				memcpy(node_new.a,node.a,sizeof(node.a));				
				swap(node_new.a[index],node_new.a[index_new]);
				for(int j = 0; j<9; j++){
					sum = sum*10 + node_new.a[j];
				}
				if(mp[sum] == 0){
					mp[sum] = cnt++;
					node_new.step = node.step+1;
					if(memcmp(arr,node_new.a,sizeof(arr)) == 0){
						return node_new.step;
					}
					que.push(node_new);
				}
			}
		}
		//if !vis[i] ...que.push
	}
}
int main()
{
	int sum1 = 0, cnt = 0, sum = 0;
	for(int i = 1; i<=8; i++){
		sum1 = sum1*10 + i;
		start[i-1] = i; 
	}
	sum1 = sum1*10;
	start[8] = 0;
	mp[sum1] = cnt++;
	for(int i = 0; i<9; i++){
		scanf("%d",&arr[i]);
		sum = sum*10 + arr[i];
	}
	if(sum == sum1) printf("0\n");
	else{
		printf("%d\n",bfs());
	}
	
	return 0;
}

```