// ------ Includes ------ //

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

using namespace std;


// ------ Directions ------ //

const int dx[4] = { 0, 1, 0, -1 };
const int dy[4] = { 1, 0, -1, 0 };


// ------ BFS ------ //

int BFS(vector<vector<int> > p)
{
	// ------ Initialize ------ //

	vector<vector<int> > lastboard = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 0 } };

	map<vector<vector<int> >, int> D;

	queue<pair<vector<vector<int> >, int> > que;

	D[p] = 1; que.push(make_pair(p, 1));


	// ------ Search ------ //

	if (p == lastboard)
	{
		return 0;
	}

	while (!que.empty())
	{
		pair<vector<vector<int> >, int> p1 = que.front(); que.pop();


		// ------ 0 Searching ------ //

		int tx = -1, ty = -1;

		for (int i = 0; i < p1.first.size(); i++)
		{
			for (int j = 0; j < p1.first[i].size(); j++)
			{
				if (p1.first[i][j] == 0)
				{
					tx = j; ty = i;
				}
			}
		}


		// ------ Moving ------ //

		for (int dir = 0; dir < 4; dir++)
		{
			if (0 <= tx + dx[dir] && tx + dx[dir] < p1.first[0].size() && 0 <= ty + dy[dir] && ty + dy[dir] < p1.first.size())
			{
				vector<vector<int> > p2 = p1.first;

				swap(p2[ty][tx], p2[ty + dy[dir]][tx + dx[dir]]);

				if (D[p2] == 0)
				{
					if (p2 == lastboard)
					{
						return p1.second;
					}

					D[p2] = p1.second + 1;

					que.push(make_pair(p2, p1.second + 1));
				}
			}
		}
	}

	return -1;
}

int main()
{
	vector<vector<int> > board(3, vector<int>(3, -1));;

	for (int i = 0; i < board.size(); i++)
	{
		for (int j = 0; j < board[i].size(); j++)
		{
			cin >> board[i][j];
		}
	}

	cout << BFS(board) << endl;

	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
// ------ Includes ------ //

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

using namespace std;


// ------ Directions ------ //

const int dx[4] = { 0, 1, 0, -1 };
const int dy[4] = { 1, 0, -1, 0 };


// ------ BFS ------ //

int BFS(vector<vector<int> > p)
{
	// ------ Initialize ------ //

	vector<vector<int> > lastboard = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 0 } };

	map<vector<vector<int> >, int> D;

	queue<pair<vector<vector<int> >, int> > que;

	D[p] = 1; que.push(make_pair(p, 1));


	// ------ Search ------ //

	if (p == lastboard)
	{
		return 0;
	}

	while (!que.empty())
	{
		pair<vector<vector<int> >, int> p1 = que.front(); que.pop();


		// ------ 0 Searching ------ //

		int tx = -1, ty = -1;

		for (int i = 0; i < p1.first.size(); i++)
		{
			for (int j = 0; j < p1.first[i].size(); j++)
			{
				if (p1.first[i][j] == 0)
				{
					tx = j; ty = i;
				}
			}
		}


		// ------ Moving ------ //

		for (int dir = 0; dir < 4; dir++)
		{
			if (0 <= tx + dx[dir] && tx + dx[dir] < p1.first[0].size() && 0 <= ty + dy[dir] && ty + dy[dir] < p1.first.size())
			{
				vector<vector<int> > p2 = p1.first;

				swap(p2[ty][tx], p2[ty + dy[dir]][tx + dx[dir]]);

				if (D[p2] == 0)
				{
					if (p2 == lastboard)
					{
						return p1.second;
					}

					D[p2] = p1.second + 1;

					que.push(make_pair(p2, p1.second + 1));
				}
			}
		}
	}

	return -1;
}

int main()
{
	vector<vector<int> > board(3, vector<int>(3, -1));;

	for (int i = 0; i < board.size(); i++)
	{
		for (int j = 0; j < board[i].size(); j++)
		{
			cin >> board[i][j];
		}
	}

	cout << BFS(board) << endl;

	return 0;
}
```