Kostka
Limit pamięci: 64MB
Kostka to gra, która toczy się na dwuwymiarowej prostokątnej planszy z kwadratowymi polami. Na każdym polu widnieje liczba
naturalna. W grze chodzi o to, żeby dojść z pola początkowego do pola końcowego, przestrzegając pewnych zasad:
- Po pierwsze poruszach
się sześcianem (ala kostka do gry), tocząc nim. Czyli obracasz sześcian wzdłuż jednej z krawędzi dolnej ściany, aż stabilnie spocznie
na którymś z sąsiednich pól (definiujemy to jako ruch na to pole). Sześcian ma na każdej ścianie jedną liczbę naturalną.
- Po drugie nie można wykonać ruchu na dane pole, jeśli ściana, która będzie
się z nim stykać (czyli będzie ścianą dolną sześcianu po obrocie), i liczba na tym polu są względnie pierwsze (ich NWD równe 1).
- Po trzecie nie można wyjść za planszę.
Gra na tyle Ci się spodobała, że postanowiłeś sobie ją utrudnić i próbujesz skończyć grę,
wykonując jak najmniejszą liczbę ruchów (dojść z pola początkowego do końcowego). Niestety, ręcznie
nie umiesz zweryfikować, czy twoja rozgrywka była optymalna, dlatego stwierdziłeś,
że napiszesz program, który Ci w tym pomoże.
Zadanie:
Napisz program, który:
- wczyta opis planszy, pozycje pola startowego i końcowego
- wyznaczy ile minimalnie trzeba wykonać ruchów, żeby skończyć grę
- wypisze wynik na standardowe wyjście
Wejście:
W pierwszej linii znajduje się sześć liczb naturalnych, wynoszących co najwyżej 1000. Są to liczby, znajdujące się na sześcianie.
Po kolei: przednia, tylna, lewa, prawa, górna i dolna ściana. Dolna ściana to ta, która będzie stykać się z polem startowym. Natomiast
przednia ściana to ta, która skierowana jest w stronę góry planszy (czyli pól o mniejszych numerach wierszy). Pole w lewym górnym rogu planszy
ma numer wiersza i numer kolumny 1.
W następnej linii wejścia są dwie liczby: n i m (1 <= n, m <= 400). Oznaczają one odpowiednio
liczbę wierszy i liczbę kolumn na planszy. W następnych
dwóch wierszach znajdują się współrzędne pola startowego i końcowego - numer wiersza i numer kolumny. Ostatnie n wierszy po m
liczb to opis planszy - każda liczba będzie wynosić co najwyżej 1018.
Wyjście:
Jedna liczba, będąca minimalną liczbą ruchów, jakie trzeba wykonać, żeby skończyć grę. Jeśli nie można skończyć gry (nie można dojść do pola
końcowego), wtedy należy wypisać -1.
Przykład:
wejście:
11 5 13 3 7 2
3 4
1 1
1 3
2 3 2 1
1 5 77 11
1 1 7 13
wyjście:
8
Wyjaśnienie przykładu:
| 1 | 2 | 3 | 4 |
| 1 | 2 | 3 | 2 | 1 |
| 2 | 1 | 5 | 77 | 11 |
| 3 | 1 | 1 | 7 | 13 |
Pole początkowe jest oznaczone na zielono, natomiast pole końcowe na czerwono.
Sześcian przetacza się przez następujące pola (wiersz, kolumna):
- (1, 1)
- (1, 2)
- (2, 2)
- (2, 3)
- (2, 4)
- (3, 4)
- (3, 3)
- (2, 3)
- (1, 3)
|