Zając
Limit pamięci: 32 MB
Zając Bajtek mieszka na polanie w kształcie prostokąta o wymiarach metrów.
Polana ta jest podzielona na pól - kwadratów o boku długości metra.
Na niektórych polach znajdują się kopce kreta, które Bajtek zawsze omija.
Każdy skok Bajtka ma długość dokładnie , a ponieważ Bajtek jest
strasznym pedantem - zawsze chce skoczyć dokładnie na środek pola.
Tak więc z pola o współrzędnych (, ) Bajtek może skoczyć tylko na pola
o współrzędnych: , ,
, , , ,
lub , o ile nie wiąże się to z wyskoczeniem
poza polanę.
Bajtek chciałby jak najszybciej dotrzeć do swojej nory, nie skacząc na pola, na których
znajdują się kopce kreta.
Mając dane pole, na którym stoi Bajtek, oraz pole, na którym znajduje się jego nora,
pomóż mu obliczyć minimalną liczbę skoków, jakie musi wykonać, aby dotrzeć do nory.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz oddzielone pojedynczym
odstępem (, ), oznaczające rozmiary polany.
Kolejne wierszy zawiera po znaków oznaczających poszczególne pola polany:
-
"." oznacza wolne pole, czyli takie, na które Bajtek może wskoczyć,
-
"x" oznacza pole, na którym znajduje się kopiec kreta,
-
"z" oznacza pole, na którym obecnie stoi zając Bajtek,
-
"n" oznacza, że na tym polu jest nora Bajtka.
Możesz założyć, że dokładnie jedno pole polany jest oznaczone jako "
z"
oraz dokładnie jedno pole jest oznaczone jako "
n".
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia powinna znaleźć się jedna dodatnia liczba
całkowita równa minimalnej liczbie skoków, jakie Bajtek musi wykonać, aby dotrzeć
do swojej nory, lub słowo "NIE", jeśli dotarcie Bajtka do nory przy użyciu
poprawnych skoków nie jest możliwe.
Przykład
Dla danych wejściowych:
4 5
.zx.x
.xx..
..x.x
x..n.
poprawną odpowiedzią jest:
3
Autor zadania: Oskar Wantoła.