Game#777
Surely everyone is familiar with the children's game "Fifteen Puzzle." In this problem, we'll consider a simpler game—the "Eight Puzzle." The game board is a 3 \times 3 square grid. There are square tiles, numbered from to . These tiles are placed in the grid cells in any random order. One cell remains empty. In one move, you can slide any adjacent tile (that is, a tile standing to the right, left, above, or below the empty cell) into the empty cell. The goal of the game is to rearrange all the tiles into the correct order by moving them as described above:
The digit represents the empty cell. Given the initial arrangement of the tiles, you are required to determine the minimal number of moves needed to arrange the tiles in the correct order.
The input file contains the initial position in the game. The position is specified by three lines, each containing three digits without spaces. The digits through are used to specify the position. Each digit appears exactly once.
The only line of the output file should contain the minimal number of moves needed to arrange the tiles in the correct order. If the input is such that it is impossible to arrange the tiles, output (minus one). The output should end with a newline character.
Example 1