Powiedzmy, że widziałeś, jak znajomy wprowadza swoje hasło do swojego telefonu z Androidem. Nie pamiętasz, jak zrobili wzór, ale pamiętasz, jak wygląda wzór. Będąc zaniepokojonym przyjacielem, którym jesteś, chcesz wiedzieć, jak bezpieczne jest jego hasło. Twoim zadaniem jest obliczyć wszystkie sposoby wykonania określonego wzoru.
Jak działają wzorce Androida
Wzory są rysowane na siatce 3 x 3 węzłów. We wzorze odwiedza się szereg węzłów, nie podnosząc nigdy palca z ekranu. Każdy odwiedzany węzeł jest połączony krawędzią z poprzednim węzłem. Należy pamiętać o dwóch zasadach.
Nie możesz odwiedzić żadnego węzła więcej niż raz
Krawędź nie może przechodzić przez nieodwiedzony węzeł
Pamiętaj, że chociaż zazwyczaj bardzo trudny do wykonania, a zatem niezbyt powszechny w prawdziwych kombinacjach blokad Androida, można poruszać się jak rycerz . Oznacza to, że możliwe jest przejście z jednej strony do niesąsiadującego rogu lub na drugą stronę. Oto dwa przykłady wzorców wykorzystujących taki ruch:
Oto animowany gif, który jest wykonywany.
Rozwiązywanie wzoru
Typowy wzór może wyglądać mniej więcej tak:
Z prostym wzorem takim jak ten istnieją dwa sposoby narysowania wzoru. Możesz zacząć od jednego z dwóch luźnych końców i podróżować przez podświetlone węzły do drugiego. Chociaż jest to prawdą w przypadku wielu wzorców, szczególnie tych, które zwykle stosują ludzie, nie dotyczy to wszystkich wzorców.
Rozważ następujący wzór:
Istnieją dwa natychmiast rozpoznawalne rozwiązania. Jeden zaczyna się w lewym górnym rogu:
I jeden zaczynający się w dolnej środkowej części:
Ponieważ jednak linia może przechodzić przez punkt, który już został wybrany, w górnym środkowym środku pojawia się dodatkowy wzór:
Ten konkretny wzór ma 3 rozwiązania, ale wzory mogą mieć od 1 do 4 rozwiązań [potrzebne źródło] .
Oto kilka przykładów:
1.
2)
3)
4
I / O
Węzeł może być reprezentowany jako liczby całkowite od zera do dziewięciu włącznie, ich ciągi znaków lub znaki od a do i (lub od A do I). Każdy węzeł musi mieć unikalną reprezentację z jednego z tych zestawów.
Rozwiązanie będzie reprezentowane przez uporządkowany kontener zawierający reprezentacje węzłów. Węzły muszą być zamawiane w tej samej kolejności, w jakiej są przekazywane.
Wzór będzie reprezentowany przez nieuporządkowany kontener par węzłów. Każda para reprezentuje krawędź rozpoczynającą się od połączenia dwóch punktów w parze. Reprezentacje wzorów nie są unikalne.
Przyjmiesz reprezentację wzorca jako dane wejściowe za pomocą standardowych metod wprowadzania i wyświetlisz wszystkie możliwe rozwiązania, które tworzą ten sam wzór za pomocą standardowych metod wyjścia.
Możesz założyć, że każde wejście będzie miało co najmniej jedno rozwiązanie i połączy co najmniej 4 węzły.
Możesz zdecydować się na użycie zamówionego kontenera zamiast nieuporządkowanego, jeśli chcesz lub jesteś zmuszony przez wybór języka.
Przypadki testowe
Z węzłami ułożonymi w następujący wzór:
0 1 2
3 4 5
6 7 8
Niech {...}stanie się nieuporządkowanym pojemnikiem, [...]będzie zamówionym pojemnikiem i (...)będzie parą.
Następujące wejścia i wyjścia powinny się zgadzać
{(1,4),(3,5),(5,8)} -> {[1,4,3,5,8]}
{(1,4),(3,4),(5,4),(8,5)} -> {[1,4,3,5,8]}
{(0,4),(4,5),(5,8),(7,8)} -> {[0,4,5,8,7],[7,8,5,4,0]}
{(0,2),(2,4),(4,7)} -> {[0,1,2,4,7],[1,0,2,4,7],[7,4,2,1,0]}
{(0,2),(2,6),(6,8)} -> {[0,1,2,4,6,7,8],[1,0,2,4,6,7,8],[8,7,6,4,2,1,0],[7,8,6,4,2,1,0]}
{(2,3),(3,7),(7,8)} -> {[2,3,7,8],[8,7,3,2]}
{(0,7),(1,2),(1,4),(2,7)} -> {[0,7,2,1,4],[4,1,2,7,0]}
{(0,4),(0,7),(1,3),(2,6),(2,8),(3,4),(5,7)} -> {[1,3,4,0,7,5,8,2,6]}
{(1,3),(5,8)} -> {}
Album imgur wszystkich przypadków testowych, jak zdjęcia można znaleźć tutaj . Wzory są w kolorze niebieskim rozwiązania w kolorze czerwonym.
Punktacja
To jest kod golfowy. Wygrywa najmniej bajtów.