Polish version    English version  
  O olimpiadzie -> Zadania -> II OI 1994/1995


 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
II Olimpiada Informatyczna 1994/95

Zadanie: KPK
Autor: Piotr Chrząstowski-Wachtel
Klub Prawoskrętnych Kierowców

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.IN
8 9
010011101
011010101
000000000
111010101
101000100
111010101
000000000
101011111
2 6
1 3
w pliku KPK.OUT należy zapisać:
NIE
Dla pliku KPK.IN
8 9
010011101
011010101
000000000
111010101
101000100
111010101
000000000
101011111
2 6
3 8
w 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.





Wersja do druku