Problem description
Jasio znalazł na ulicy bardzo stary telefon – Nokię 3310. Skontaktował się z właścicielemi i umówił się, żeby ją jutro oddać. Jasio niestety nie powstrzymał się i sprawdził, że w telefonie zainstalowana jest gra Snake. Wariant gry zainstalowany na komórce jest odrobinę inny niż zwykle i Jasio nie potrafi go wygrać.
Plansza do gry składa się z pól następujących rodzajów:
- zwykłe (
.) – można po nich chodzić, - zabronione (
#) – wejście w nie powoduje przegraną, - z jabłkiem (
J) – wejście w nie powoduje wydłużenie węża o jeden segment.
Wąż składa się z k ≥ 1
segmentów ponumerowanych kolejnymi liczbami naturalnymi. Głowa węża
znajduje się w miejscu segmentu numer 1. Przy poruszaniu się, głowa węża
przemieszcza się najpierw, natychmiast potem jednocześnie każdy segment
zajmuje miejsce segmentu o numerze o jeden mniejszym. Jasio steruje
głową: w każdym ruchu może nacisnąć jedną ze strzałek: prawo, lewo, góra
lub dół i głowa węża przemieści się wtedy w tym kierunku. Początkowo wąż
składa się tylko z głowy, zakładamy, że pod nią jest zwykłe pole
(.).
Ruchy węża ograniczone są następującymi warunkami:
- wąż nie może wyjść głową poza planszę,
- wąż nie może przechodzić przez pola zabronione
(
#), - wąż może zjadać jabłka (
J), zjedzone jabłko znika i zamienia się w zwykłe pole (.), a wąż wydłuża się o jeden segment (k + 1-szy segment pojawia się w polu, w którym wcześniej, przed ruchem, był k-ty segment), - głowa skręca o 0∘, 90∘ lub − 90∘ w stosunku do poprzedniego ruchu, pierwszy ruch można wykonać w dowolnym kierunku,
- dwa segmenty węża nie mogą być jednocześnie na jednym polu (dozwolone jest jednak, że głowa przemieści się na pole, na którym wcześniej był ostatni segment węża).
Aby wygrać, Jasio musi zjeść wężem wszystkie jabłka. Chciałby dokonać tego w jak najmniejszej liczbie ruchów. Ile ich potrzeba?
Napisz program, który wczyta sytuację na planszy do gry w Snake, wyznaczy optymalne rozwiązanie i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym (jedynym) wierszu wejścia znajdują się dwie liczby
naturalne N oraz M, oddzielone pojedynczym odstępem i
określające kolejno liczbę wierszy i kolumn na planszy. W każdym z
kolejnych N wierszy znajduje
się ciąg M znaków
J, G, . lub #
(zakładamy, że G oznacza głowę węża, na planszy jest
dokładnie jeden taki symbol).
Wyjście
W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita – minimalna liczba ruchów potrzebna do zwycięstwa.
Jeżeli osiągnięcie celu jest niemożliwe, zamiast tego należy wypisać
jedno słowo NIE.
Ograniczenia
1 ≤ N, M ≤ 15.
Na planszy znajduje się co najwyżej 8 jabłek.
Przykład
| Input | Output | |
|
|