Olimpiada Informatyczna

VI Olimpiada Informatyczna 1998/99

Zadanie: MAG

Autor: Krzysztof Loryś

Magazynier

Etap III, dzień pierwszy

21 kwietnia 1999

Plik źródłowy:	`MAG.???` (np. `pas`, `c`, `cpp`)
Plik wykonywalny:	`MAG.exe`
Plik wejściowy:	`MAG.in`
Plik wyjściowy:	`MAG.out`

Podłoga magazynu jest prostokątem podzielonym na n*m 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 z pliku tekstowego MAG.IN 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,
zapisze wynik w pliku tekstowym MAG.OUT.

Wejście W pierwszym wierszu pliku wejściowego MAG.IN są zapisane dwie dodatnie liczby całkowite n i m oddzielone pojedynczym odstępem, n,m<=100. Są to rozmiary magazynu. W każdym z kolejnych n wierszy znajduje się jedno m-literowe słowo utworzone z liter S, M, P, K, w. Litera na i-tej pozycji j-tego z tych słów oznacza stan pola o współrzędnych (i,j): 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 w pliku MAG.IN dokładnie raz. Wyjście Twój program powinien zapisać w pliku wyjściowym MAG.IN: 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 pliku wejściowego MAG.IN: 10 12 SSSSSSSSSSSS SwwwwwwwSSSS SwSSSSwwSSSS SwSSSSwwSKSS SwSSSSwwSwSS SwwwwwPwwwww SSSSSSSwSwSw SSSSSSMwSwww SSSSSSSSSSSS SSSSSSSSSSSS poprawną odpowiedzią jest plik wyjściowy MAG.OUT 7