Magazynier

Limit pamięci: 32 MB

Podłoga magazynu jest prostokątem podzielonym na kwadratowych pól. Dwa pola są sąsiednie, jeśli mają wspólny bok. Na jednym z pól stoi paczka. Każde inne pole jest albo wolne, albo zajęte przez skrzynię, której magazynier nie jest w stanie poruszyć. Magazynier musi przepchnąć paczkę z pola początkowego P na pole docelowe K. Magazynier może przemieszczać się po wolnych polach, przechodząc z pola, na którym stoi, na dowolne z wolnych pól sąsiednich. Jeśli magazynier stoi na polu sąsiadującym z polem, na którym jest paczka, to może ją przepchnąć na pole sąsiednie z przeciwnej strony paczki, jeżeli jest ono wolne.

Zadanie

Napisz program, który:

  • wczyta ze standardowego wejścia plan magazynu, początkowe położenia magazyniera i paczki oraz docelowe położenie paczki,
  • obliczy minimalną liczbę przesunięć paczki przez granice pól, wymaganą do ustawienia jej w położeniu docelowym lub stwierdzi, że to jest niemożliwe,
  • wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia są zapisane dwie dodatnie liczby całkowite i oddzielone pojedynczym odstępem, . Są to rozmiary magazynu. W każdym z kolejnych wierszy znajduje się jedno -literowe słowo utworzone z liter S, M, P, K, w. Litera na -tej pozycji -tego z tych słów oznacza stan pola o współrzędnych :

  • S - skrzynia,
  • M - początkowa pozycja magazyniera,
  • P - początkowa pozycja paczki,
  • K - docelowa pozycja paczki,
  • w - wolne pole.

Każda z liter M, P i K występuje na wejściu dokładnie raz.

Wyjście

Twój program powinien wypisać na standardowe wyjście:

  • dokładnie jedno słowo NIE, jeżeli paczki nie da się umieścić w położeniu docelowym,
  • dokładnie jedną liczbę całkowitą, równą minimalnej liczbie przesunięć paczki przez granice pól, wymaganą do umieszczenia paczki w położeniu docelowym, jeżeli paczkę da się tam przepchnąć.

Przykład

Dla danych wejściowych:

10 12
SSSSSSSSSSSS
SwwwwwwwSSSS
SwSSSSwwSSSS
SwSSSSwwSKSS
SwSSSSwwSwSS
SwwwwwPwwwww
SSSSSSSwSwSw
SSSSSSMwSwww
SSSSSSSSSSSS
SSSSSSSSSSSS

poprawną odpowiedzią jest:

7

Autor zadania: Krzysztof Loryś.