In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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.