Presumably everybody knows how a knight can move on a chessboard. One may agree that its move- ments are quite monotonous, so to make them more entertaining let’s define a so called “dynamic knight”. A dynamic knight can perform many different movements that may belong to three types: • type K: two fields forward (in any direction) and one sidewise — like “regular knight”; • type B: two fields diagonally — more like a bishop; • type T: sort of teleportation to a field which is a mirror reflection with respect to any of two axes of symmetry of the chessboard (we take into consideration only axes of symmetry parallel to sides of the chessboard); The picture on the right shows all possible movements of a knight divided into three types K, B and T. Obviously our knight, like the “regular” one cannot move outside the chessboard. For a dynamic knight it is not relevant whether the fields between the starting field and ending one are occupied or not (again like for the “regular knight”). It only matters whether the ending field is empty. Then the movement can be performed. There has to be a restriction among so many capabilities of a dynamic knight. It cannot perform the same sort of movements consecutively (just not to fall into routine). Having redefined a chess knight, why not to redefine a chess- board? Our chessboard will be a square of size 2N × 2N. N can be any integer number from the range of 3..20. There can be several obstacles of any shape on a chessboard so a knight cannot stop on these defected fields. Your task is to write a program which can calculate the minimal number of movements to get the knight from one given field to another one. It may be assumed that the first movement can be of any type. Input First line contains the number N, being the size of a chessboard. The second one contains field coordinates separated by space character, which is a knight current standpoint. Upper left-hand size corner has coordinates (1, 1). Third line contains destination field for the knight. Consecutive lines contain obstacle coordinates and the line with coordinates (0, 0) ends the obstacle description. Input can contain several sets of data. Input’s end is shown as a line defining chessboard’s size as 0. Output It is supposed to be fairly simple — one line with a single number being the calculated minimal number of movements.
2/3 Sample Input 3 11 11 22 00 10 11 20 20 20 1 1 20 31 32 33 23 13 00 10 21 18 12 22 56 72 83 94 1 15 7 12 8 13 9 11 11 9 12 4 11 3 95 27 38 65 00 3 11 54 22 24 25 31 32 33 36 42 43 45
3/3 51 53 55 61 64 65 66 00 0 Sample Output Result : 0 Solution doesn't exist Result : 6 Result : 4