W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Dana jest prostokątna mapa miasta złożona z kwadratowych pól ( i ). Wiersze kwadratowych pól tworzących mapę są ponumerowane kolejno od góry do dołu liczbami od do , a kolumny od lewej do prawe, kolejno od do . 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 na przyległe pole wrócić na .
Klub Prawoskrętnych Kierowców złożył zamówienie na program komputerowy, który dla dowolnych dwóch różnych pól oraz rozstrzyga, czy można dojechać od punktu do 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 do zaliczamy również pola oraz .
Ułóż program który:
W standardowym wejściu znajdują się dwie liczby całkowite, oddzielone pojedynczym odstępem: liczba wierszy oraz liczba kolumn . W każdym z kolejnych wierszy pliku znajduje się opis odpowiedniego kolejnego wiersza mapy w postaci jednego słowa o długości utworzonego z cyfr i . Cyfra oznacza, że odpowiednie pole jest wolne a cyfra , że jest zablokowane.
Następnie w jednym wierszu są zapisane dwie współrzędne pola oddzielone pojedynczym odstępem: numer wiersza nie większy niż oraz numer kolumny nie większy niż , a w kolejnym wierszu są zapisane, w taki sam sposób, dwie współrzędne pola .
Dane w standardowym wejściu są zapisane poprawnie i Twój program nie musi tego sprawdzać.
W standardowym wyjściu należy zapisać:
Dla danych wejściowych:
8 9 010011101 011010101 000000000 111010101 101000100 111010101 000000000 101011111 2 6 1 3
poprawną odpowiedzią jest:
NIE
Dla danych wejściowych:
8 9 010011101 011010101 000000000 111010101 101000100 111010101 000000000 101011111 2 6 3 8
poprawną odpowiedzią jest:
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
Autor zadania: Piotr Chrząstowski-Wachtel.