Solve the Puzzle
Given a grid containing numbers 1, 2, 3, …, 9, you are asked to perform a sequence of swap operations to obtain the following grid:
On each move, you can swap two neighbors (neighbors in either horizontal or vertical directions). What would be the minimum number of moves required to obtain the required grid?
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
Input
The input contains 3 lines each one containing 3 numbers representing the initial grid.
Output
The program should print the minimum number of moves required to obtain the 1, 2, 3, …, 9 grid.
Examples
Input | Output |
2 1 3
7 5 9
8 4 6 | 4 |
Constraints
Time limit: 50 seconds
Memory limit: 512 MB
Output limit: 1 MB