Olimpiada Informatyczna

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

w pliku KPK.OUT należy zapisać:

NIE

Dla pliku KPK.IN

w pliku KPK.OUT należy zapisać:

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.