| Historia OI -> II OI 1994/1995 |  |
|
II Olimpiada Informatyczna 1994/95
|
|
Zadanie: KPK
|
Autor: Piotr Chrząstowski-Wachtel
|
| Zawody II stopnia |
| Plik źródłowy: | KPK.??? (np. pas, c, cpp) |
| Plik wykonywalny: | KPK.exe |
| Plik wejściowy: | KPK.in |
| Plik wyjściowy: | KPK.out |
Dana jest prostokątna mapa miasta złożona z n*m kwadratowych pól (1<=n<=100 i 1<=m<=100). Wiersze kwadratowych pól tworzących mapę są ponumerowane kolejno od góry do dołu liczbami od 1 do n, a kolumny od lewej do prawe, kolejno od 1 do m. Każde pole jest albo wolne albo zablokowane. Ruch kołowy jest dozwolony tylko po wolnych polach. Z każdego wolnego pola można przejechać na wolne pole przyległe (tzn. takie, które ma z danym polem wspólny bok), nie można jednak zawracać, to znaczy bezpośrednio po przejechaniu z pola X na przyległe pole Y wrócić na X.
Klub Prawoskrętnych Kierowców złożył zamówienie na program komputerowy, który dla dowolnych dwóch różnych pól A oraz B rozstrzyga, czy można dojechać od punktu A do B nie wykonując ani jednego skrętu w lewo, a jeśli tak, znajduje jedną taką drogę o minimalnej długości. Długość drogi jest to liczba wszystkich jej pól. Do drogi od A do B zaliczamy również pola A oraz B.
Zadanie
Ułóż program który:- wczytuje z pliku tekstowego KPK.IN dane o prostokątnej sieci pól (tzn. liczbę wierszy n, liczbę kolumn m i stan każdego pola, a następnie współrzędne dwóch różnych pól A i B;
- rozstrzyga, czy istnieje droga bez skrętów w lewo od pola A do B i jeśli nie, to zapisuje w pliku tekstowym KPK.OUT jedno słowo NIE, a jeśli tak, to znajduje jedną taką drogę o minimalnej długości i zapisuje ją w pliku KPK.OUT. Jeśli chociaż jedno z pól A, B nie jest wolne, to odpowiedzią jest NIE.
Wejście
W pierwszym pliku KPK.IN znajdują się dwie liczby całkowite, oddzielone pojedynczym odstępem: liczba wierszy n oraz liczba kolumn m. W każdym z kolejnych n wierszy pliku znajduje się opis odpowiedniego kolejnego wiersza mapy w postaci jednego słowa o długości m utworzonego z cyfr 0 i 1. Cyfra 0 oznacza, że odpowiednie pole jest wolne a cyfra 1, że jest zablokowane.Następnie w jednym wierszu są zapisane dwie współrzędne pola A oddzielone pojedynczym odstępem: numer wiersza nie większy niż n oraz numer kolumny nie większy niż m, a w kolejnym wierszu są zapisane, w taki sam sposób, dwie współrzędne pola B.
Dane w pliku KPK.IN są zapisane poprawnie i Twój program nie musi tego sprawdzać.
Wyjście
W pliku KPK.OUT należy zapisać:- albo jedno słowo NIE, gdy nie istnieje droga bez skrętów w lewo od A do B, lub przynajmniej jedno z pól A, B jest zablokowane,
- albo opis jednej drogi bez skrętów w lewo od A do B o minimalnej długości; w tym przypadku w pierwszym wierszu należy wpisać długość drogi d, a w każdym z kolejnych d wierszy dwie współrzędne kolejnego pola drogi oddzielone pojedynczym odstępem.
Przykłady
Dla następującego pliku KPK.IN8 9 010011101 011010101 000000000 111010101 101000100 111010101 000000000 101011111 2 6 1 3w pliku KPK.OUT należy zapisać:
NIEDla pliku KPK.IN
8 9 010011101 011010101 000000000 111010101 101000100 111010101 000000000 101011111 2 6 3 8w pliku KPK.OUT należy zapisać:
12 2 6 3 6 4 6 5 6 5 5 5 4 4 4 3 4 3 5 3 6 3 7 3 8
Twój program powinien szukać pliku KPK.IN w katalogu bieżącym i tworzyć plik KPK.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę KPK.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonywalnej powinien być zapisany w pliku KPK.EXE.