#include<iostream>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=1000010;
const int MOD=1000007;
string st;
string en="123456780";
int head[MAXN],nex[MAXN];
int f[MAXN],top;
string ss[MAXN];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
queue<string> q;
queue<int> qs;
void input()
{
	memset(head,-1,sizeof(head));
	memset(nex,-1,sizeof(nex));
	for(int i=0;i<3;i++)
	    for(int j=0;j<3;j++){
	    	char c;
	        cin>>c;
	        st+=c;
	    }
	//cout<<st<<endl;
}

int has(string s){
	int sum(0);
	for(int i=0;i<9;i++){
		sum*=10;
		sum+=s[i]-'0';
	}
	return sum;
}

void add(string tt){
	int tmp=has(tt);
	nex[top]=head[tmp%MOD];
	head[tmp%MOD]=top;
	ss[top++]=tt;
}

bool ff(string tt){
	int tmp=has(tt);
	int u=head[tmp%MOD];
	while(u!=-1){
		string ttt=ss[u];u=nex[u];
		if(ttt==tt) return true;
	}
	return false;
}

void xxj()
{
	q.push(st);
	add(st);
	qs.push(0);
	while(!q.empty()){
		string tmp=q.front();q.pop();
		int ts=qs.front();qs.pop();
		//if(ts==4) cout<<tmp<<' '<<ts<<endl;
		if(tmp==en) {cout<<ts<<endl;return;}
		int pos=tmp.find('0');
		int x=pos/3,y=pos%3;
		//cout<<x<<' '<<y<<endl;
		for(int k=0;k<4;k++){
			int xx=x+dx[k];
			int yy=y+dy[k];
			if(xx<0 || yy<0 || xx>=3 || yy>=3) continue;
			string tt=tmp;
			swap(tt[xx*3+yy],tt[pos]);
			if(!ff(tt)){
				q.push(tt);
				qs.push(ts+1);
				add(tt);
			}
		}
	}
}

int main()
{
	input();
	xxj();
	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<string>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=1000010;
const int MOD=1000007;
string st;
string en="123456780";
int head[MAXN],nex[MAXN];
int f[MAXN],top;
string ss[MAXN];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
queue<string> q;
queue<int> qs;
void input()
{
	memset(head,-1,sizeof(head));
	memset(nex,-1,sizeof(nex));
	for(int i=0;i<3;i++)
	    for(int j=0;j<3;j++){
	    	char c;
	        cin>>c;
	        st+=c;
	    }
	//cout<<st<<endl;
}

int has(string s){
	int sum(0);
	for(int i=0;i<9;i++){
		sum*=10;
		sum+=s[i]-'0';
	}
	return sum;
}

void add(string tt){
	int tmp=has(tt);
	nex[top]=head[tmp%MOD];
	head[tmp%MOD]=top;
	ss[top++]=tt;
}

bool ff(string tt){
	int tmp=has(tt);
	int u=head[tmp%MOD];
	while(u!=-1){
		string ttt=ss[u];u=nex[u];
		if(ttt==tt) return true;
	}
	return false;
}

void xxj()
{
	q.push(st);
	add(st);
	qs.push(0);
	while(!q.empty()){
		string tmp=q.front();q.pop();
		int ts=qs.front();qs.pop();
		//if(ts==4) cout<<tmp<<' '<<ts<<endl;
		if(tmp==en) {cout<<ts<<endl;return;}
		int pos=tmp.find('0');
		int x=pos/3,y=pos%3;
		//cout<<x<<' '<<y<<endl;
		for(int k=0;k<4;k++){
			int xx=x+dx[k];
			int yy=y+dy[k];
			if(xx<0 || yy<0 || xx>=3 || yy>=3) continue;
			string tt=tmp;
			swap(tt[xx*3+yy],tt[pos]);
			if(!ff(tt)){
				q.push(tt);
				qs.push(ts+1);
				add(tt);
			}
		}
	}
}

int main()
{
	input();
	xxj();
	return 0;
}
```