URI Online Judge | 1952

Knight in 3D Chess

By Leandro Zatesko, UFFS BR Brazil

Timelimit: 1

In the case you do not know it, the student Alesom Zorzi, one of our heroes of AKM (UFFS's team which has got 6 balloons in the First Phase of ICPC Latin America Brazilian Subregional Contest), is a chess player, having also conquered some medals in important tournaments.

Of the pieces of chess, one of the most interesting is the knight, which can jump from a position of coordinates (i1, j1) to one of coordinates (i2, j2) if and only if {|i1 - i2|, |j1 - j2|} = {1, 2}.

Based on Star Trek series, Alesom has developed his own variant of 3D Chess, in which the game consists of not 1, but L boards of dimensions N × M, each board at a level numbered from 1 to L. By the way, the lines from each level are numbered from 1 to N, as the columns from 1 to M, so each game position can be identified by a triple of coordinates (i, j, k), wherein i is the index of the line, j is the index of the column and k is the index of the level. A knight in this variant of 3D Chess can jump from a position of coordinates (i1, j1, k1) to one of coordinates (i2, j2, k2) if and only if {|i1 - i2|, |j1 - j2|, |k1 - k2|} = {0, 1, 2}. The figure illustrates a knight at position (5, 5, 1) in a game with 3 levels of dimensions 8 × 8, highlighting its adjacent positions.


The first input line contains only the integers N, M and L (8 ≤ N, M ≤ 100, 3 ≤ L ≤ 100). The second line contains a triple of coordinates (i1, j1, k1), and the third line contains a triple of coordinates (i2, j2, k2) (1 ≤ i1, i2N, 1 ≤ j1, j2M, 1 ≤ k1, k2L).


Output a line containing a single integer, which represents the minimum number of moves needed for a knight to go from the position (i1, j1, k1) to the position (i2, j2, k2).

Input Sample Output Sample

8 8 3
5 5 1
3 4 2