The Grid

Time Limit: 1 Second
Memory Limit: 32768 KB

Some days ago, a game called "The grid" was introduced to watashi. It is a simple
game, but not an easy one. The game is played on a three-dimensional grid, which
contains *P* * *Q* * *R* lattices. And there are *N*
numbers (from 1 to *N*) in these lattices, except an empty one, each lattice
contains a distinct number, so here we have *N* = *P* * *Q*
* *R* - 1. In each step, the player can move a number in a lattice, which
is adjacent to the empty one, to the empty lattice. So after one step, the number
player moved will change its position, and the old position of it will be empty.
*N*ow the task is: you've given a start state of the three-dimensional grid
and an end state of the grid, start from the start state, find a way to the end
state, using moving method described above.

But you know, watashi will never be satisfied at his achievement, so he wants to
know how many steps can he finish the game at least. To simplify the problem, he
likes the end state to be the same simple state, which described in the following
section.

**Input**

Input consists of several testcases(not exceed 50), each testcase starts with a
line contains three integers: *P*, *Q* and *R*. Then followed
by *P* blocks, each block contains *Q* lines, and each line contains
*R* integers. These *P* * *Q* * *R* integers will be
distinct, and the empty lattice will be marked by integer *P* * *Q*
* *R*. These *P* blocks described the start state. The end state of
each testcase will not be described in input, because they will be the same. So if
it is described in method just like start state, integers will be placed from 1 to
*P* * *Q* * *R* in ascending order. For example, if *P*
= 3, *Q* = *R* = 2, the end state will be like this:

1 2
3 4
5 6
7 8
9 10
11 12

We guarantee that 1 <= *P* <=4, 1 <= *Q* <= 4, 1 <=
*R* <= 4.

**Output**

For each testcase, you should output the minimum number of steps to get to the end
state from the start state in one line. If there isn't any way to get to the end
state from the start state, output -1 please.

**Sample Input**

2 2 2
1 8
3 2
5 6
7 4

**Sample Output**

2

Author:

**FAN, Yuzhe**
Source:

**ZOJ Monthly, December 2008**
Submit
Status