Uwaga! Poniższe rozwiązanie jest niepoprawne ponieważ Mariusz zmodyfikował zadanie po moich testach. Dzisiaj wrzucę poprawione omówienie. Przepraszam za wprowadzenie w błąd.
W tym zadaniu naszym celem jest stwierdzenie czy istnieje spójny niepusty podciąg trasy Jasia, który utworzy pętlę.
Pierwsze spostrzeżenie jest takie, że trasa jaką pokonał Jasiu jest krótka i zawiera co najwyżej 100 znaków, a zatem spokojnie możemy zbadać wszystkie możliwe podciągi.
Przejdźmy zatem do weryfikacji czy dany podciąg jest poprawną pętlą (łamaną). Sprawdźmy definicję łamanej.
Łamaną nazywamy figurę geometryczną, która jest sumą skończonej liczby odcinków takich, że każde dwa kolejne mają wspólny koniec oraz:
- każde dwa kolejne odcinki i tylko dwa kolejne odcinki mają wspólny koniec,
- żadne dwa następujące po sobie odcinki nie są zawarte w jednej prostej.
Zgodnie z treścią zadania nasz bohater może na trasie wykonywać skręty o 90 lub 180 stopni. Jednak jak widzimy w definicji łamanej nawroty (skręty o 180 stopni) spowodują, że dana figura nie będzie już łamaną ponieważ 2 następujące po sobie odcinki będą zawarte w jednej prostej. I to jest główny haczyk w tym zadaniu. W związku z powyższym pierwszym etapem jest sprawdzenie czy w wybranym podciągu trasy występują nawroty czyli: NS, SN, WE lub EW. Jeżeli występują to dany podciąg nie będzie poprawną pętlą.
Jeżeli nawroty nie występują to pozostało nam sprawdzić czy po przejściu całego podciągu wróciliśmy do punktu, z którym się zaczynał. Można to zrobić np. zliczając liczbę wystąpień liter N, S, E, W. Jeżeli N = S i E = W tzn. że wróciliśmy do punktu wyjścia, a co za tym idzie znaleźliśmy poprawną pętlę.
Wybranie podciągu do sprawdzenia ma złożoność O(n^2), sprawdzenie tego podciągu O(n), a zatem całość ma złożoność O(n^3) co przy maksymalnej wartości n = 100 jest w zupełności wystarczające.
Ale myślę, że nawet pomimo takiej wtopy mój wynik jest o.k. tym bardziej, że od dawna nie robiłem zadań tego typu.
