Robinson

Limit pamięci: 256 MB

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

Zadanie polega na napisaniu programu, który:

• wczyta ze standardowego wejścia opis mapy,
• obliczy minimalną liczbę ruchów łodzi potrzebnych do wypłynięcia poza obszar pokazany na mapie,
• wypisze obliczoną liczbę na standardowe wyjście.

Wejście

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:

• "." - (kropka) oznacza pole zajęte przez wodę,
• "X" - oznacza przeszkodę (trzcinę lub kawałek lądu),
• "r" - oznacza fragment łodzi Robinsona.

Wyjście

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".

Przykład

Dla danych wejściowych:

10
..........
..........
..r.......
.rrrX.....
rrrrr.....
.rrr......
X.r.......
.Xr.......
..........
..........

poprawną odpowiedzią jest:

10

Autor zadania: Karol Cwalina.