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.
Rzucony przez sztorm na bezludną wyspę Robinson zbudował łódkę, na której postanowił wypłynąć w morze i szukać ludzkich siedzib. Jest on doświadczonym żeglarzem, więc jego łódź jest zbudowana zgodnie z zasadami sztuki: ma wzdłużną oś symetrii oraz odpowiedni kształt. Na dziobie jest wąska, stopniowo rozszerza się w stronę środka, by z kolei zacząć się zwężać w kierunku rufy. W szczególności oznacza to, że w pewnym miejscu w środku łódź jest szersza niż na dziobie i na rufie.
Pech chciał, że w miejscu, w którym Robinson spuścił swoją łódź na wodę, rosną bardzo gęste trzciny. Co gorsza, są one tak sztywne, że łódź nie jest w stanie ich złamać i przepłynąć przez zajmowane przez trzciny miejsca. Być może odpowiednio manewrując łodzią, Robinson jest w stanie wypłynąć na otwarte morze.
Ze względu na słabą manewrowość, łódź może się poruszać do przodu, do tyłu, w prawo oraz w lewo, ale nie może skręcać. Oznacza to, że może się zdarzyć sytuacja, gdy łódź porusza się rufą lub którąś burtą do przodu.
Twoim zadaniem jest ocenić, czy Robinson może się wydostać na pełne morze.
Dla uproszczenia, wyspa wraz z otoczeniem jest w zadaniu reprezentowana przez kwadratową mapę podzieloną na kwadratowe pola jednostkowe, z których każde może być zajęte przez wodę, kawałek łodzi Robinsona, bądź przez przeszkodę (np. ląd lub trzcinę). Łódź jest ustawiona równolegle do jednego z czterech kierunków Świata i właśnie w tym kierunku przebiega przez środek łodzi pas pól jednostkowych, idealnie przepołowionych wzdłużną osią symetrii łodzi.
Przyjmujemy, że poza mapą znajduje się otwarte morze. Robinson może wypłynąć na otwarte morze, jeżeli łódź jest w stanie w całości opuścić teren pokazany na mapie. Pojedynczy ruch to przesunięcie się łodzi o jedno pole w wybranym kierunku (północ, południe, wschód lub zachód). Aby ruch był wykonalny, przed i po wykonaniu ruchu łódź musi w całości znajdować się na wodzie.
Zadanie polega na napisaniu programu, który:
Pierwszy wiersz zawiera jedną liczbę całkowitą , oznaczającą długość boku mapy. W każdym z następnych wierszy znajduje się po znaków opisujących kolejne pola mapy: -ty znak w wierszu numer określa zawartość pola o współrzędnych . W wierszu mogą się pojawić następujące znaki:
Twój program powinien wypisać (w pierwszym i jedynym wierszu standardowego wyjścia) jedną dodatnią liczbę całkowitą, równą najmniejszej koniecznej liczbie ruchów łodzi niezbędnych do opuszczenia przez łódź w całości terenu przedstawionego na mapie. Jeśli wypłynięcie na otwarte morze nie jest możliwe, należy wypisać słowo "NIE".
Dla danych wejściowych:
10 .......... .......... ..r....... .rrrX..... rrrrr..... .rrr...... X.r....... .Xr....... .......... ..........
poprawną odpowiedzią jest:
10
Autor zadania: Karol Cwalina.