|
|||||||||||||||
|
Klub Prawoskrętnych Kierowców
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.
ZadanieUłóż program który:
WejścieW 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ścieW pliku KPK.OUT należy zapisać:
PrzykładyDla 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.
|