Polish version    English version  
  O olimpiadzie -> Zadania -> VI OI 1998/1999


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
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




Wersja do druku