Niedawno rozpoczęto prace nad nową grą o nazwie Szachy 3D. Jak łatwo się domyślić, szachownica w nowej grze została poszerzona o jeden wymiar w stosunku do tradycyjnych szachów. Ciągle trwają jednak badania nad tym, jakie powinny być jej optymalne rozmiary, i jaki zestaw bierek. Wydaje się, że wszystko skończy się na rozmiarach 8*8*8, ale nie jest to jeszcze przesądzone. Jednym z pasjonatów nowej gry jest kapitan Mambeks. Jako hobby prowadzi on badania nad optymalnym zestawem bierek. Aktualnie pracuje nad ruchami superskoczka. Superskoczek jest bierką, która nieco przypomina swoimi ruchami swego protoplastę. Jednak w związku z wprowadzeniem trzeciego wymiaru, jego ruchy trzeba było nieco zmodyfikować. Superskoczek może wykonywać ruchy trzech różnych typów:
Dla superskoczka, tak jak dla zwykłego skoczka, nie jest istotne czy jakaś bierka znajduje pomiędzy polami, z którego startuje, i na którym kończy ruch. Istotne jest tylko to, aby pole na które ruch prowadzi było puste - wtedy ruch może być wykonany. Superskoczek, oprócz tak wielu możliwości, ma również jedną drobne ograniczenie. Nie zawsze może wykonać dowolny ruch, a ściślej nigdy po ruchu jakiegoś typu nie może wykonać ruchu tego samego typu (rutyna to straszna rzecz).
Dla przykładu poniżej pokazano wszystkie możliwe ruchy superskoczka stojącego na polu o współrzędnych (2, 3, 4) przy założeniu, że szachownica ma rozmiary 8*8*8 (numeracja pól rozpoczyna się od (1, 1, 1)).
| Ruchy zwykłego skoczka | Ruchy pomiędzy płaszczyznami | Teleportacja |
| (4, 4, 4) | (3, 3, 6) | (7, 3, 4) |
| (4, 2, 4) | (1, 3, 6) | (2, 6, 4) |
| (3, 5, 4) | (2, 4, 6) | (2, 3, 5) |
| (3, 1, 4) | (2, 2, 6) | |
| (1, 5, 4) | (3, 3, 2) | |
| (1, 1, 4) | (1, 3, 2) | |
| (2, 4, 2) | ||
| (2, 2, 2) |
Twoim zadaniem jest napisanie programu, który pomógłby kapitanowi Mambeksowi w badaniach nad tym, jaką minimalną liczbę ruchów skoczek musi wykonać, aby przemieścić się z jednego pola na inne.
Dane wejściowe mogą być złożone z wielu zbiorów. Każdy zbiór rozpoczyna wiersz zawierający liczbę całkowitą N (3 ≤ N ≤ 16) będącą rozmiarem szachownicy (szachownica jest sześcianem o rozmiarach N*N*N). Kolejne dwa wiersze zawierają współrzędne punktu startowego i końcowego. Następne wiersze opisują przeszkody znajdujące się na szachownicy. Każdy wiersz zawiera sześć liczb całkowitych dodatnich. Każda przeszkoda jest prostopadłościanem, którego jeden wierzchołek opisują pierwsze trzy liczby, a kolejne są rozmiarami jego boków. Wiersz zawierający sześć zer kończy opis przeszkód. Wiersz zawierający rozmiar szachownicy 0 jest znacznikiem końca danych wejściowych.
Dla każdego zbioru danych masz wypisać wiersz zawierający liczbę będącą minimalną liczbą kroków, w których superskoczek może się odbyć drogę od punktu startowego do końcowego. Jeżeli rozwiązanie nie istnieje, to powinieneś wypisać wartość -1.
8 1 1 1 2 3 1 0 0 0 0 0 0 8 1 1 1 8 8 8 0 0 0 0 0 0 16 2 3 4 8 8 8 1 1 1 8 1 1 3 5 6 2 2 2 3 4 4 3 3 1 1 1 4 1 2 1 7 6 8 1 1 1 6 7 8 1 1 1 7 8 6 1 1 1 8 7 6 1 1 1 8 8 1 1 1 1 8 1 8 1 1 1 1 8 8 1 1 1 0 0 0 0 0 0 0
1 5 7