Problem description
Jasio ostatnio zadarł z dresami. Niestety, planują oni zamach na niego. Jasio wie, że należy się od nich trzymać z daleka. Niestety, trzeba chodzić do szkoły. Na szczęście dresy do szkoły nie chodzą, więc siedzą w domu nie ruszając się (póki Jasio nie przejdzie odpowiednio blisko).
Dana jest prostokątna mapa z zaznaczoną pozycją Jasia, pozycjami dresów, pozycją szkoły oraz pozycjami przeszkód.
Na potrzeby tego zadania zakładamy, że odległość między dwoma punktami to minimalna liczba kroków, które należy wykonać aby przemieścić się między nimi. W jednym kroku można przejść do góry, w dół, w lewo lub w prawo o dokładnie jeden kwadrat jednostkowy.
Napisz program, który: wczyta mapę, wyznaczy największą możliwą odległość od najbliższego dresa na mapie na drodze Jasia do szkoły i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N oraz M, oddzielone pojedynczym odstępem i oznaczające kolejno: wysokość i szerokość mapy. W kolejnych N wierszach znajduje się po M znaków określających mapę. Każdy znak:
.– oznacza wolne pole,J– oznacza pozycję Jasia (znajduje się tylko jeden taki znak na mapie),D– oznacza pozycję dresa,S– oznacza pozycję szkoły (znajduje się tylko jeden taki znak na mapie),#– oznacza przeszkodę (przez nią ani dres, ani Jasio przejść nie może).
Wyjście
Twój program powinien wypisać na wyjście dokładnie jedną liczbę
całkowitą – minimalną odległość na trasie Jasia od dowolnego dresa w
optymalnym rozwiązaniu. Jeśli Jasio jest bezpieczny i żaden dres go nie
draśnie – wyjściem powinno być OK. Jeśli Jasio nie może
dostać się do szkoły (nawet przechodząc przez dom dresa) – program
powinien wypisać NIE.
Ograniczenia
1 ≤ N, M ≤ 1 000.
Przykład
| Wejście | Wyjście | |
|
|