Wyspy na trójkątnej sieci

Limit pamięci: 64 MB

Sieć trójkątów jest zbudowana z równobocznych trójkątów o boku 1. Ścieżką na sieci trójkątów nazywamy dowolny skończony ciąg trójkątów (o boku 1) sieci, taki, że każde kolejne dwa trójkąty w tym ciągu mają wspólny bok.

Figurę utworzoną przez punkty skończonej liczby trójkątów sieci nazywamy wyspą, jeśli dowolne dwa zawarte w niej trójkąty sieci można połączyć ścieżką utworzoną z trójkątów zawartych w tej figurze.

Figury przedstawione na rysunkach 1.1, 1.2 i 1.3 są wyspami. Figura na rysunku 1.4 nie jest wyspą. Figury na rysunkach 2.2, 2.3 i 2.5 są przystające.

Zamierzamy dla każdego opisać w systematyczny sposób wszystkie nieprzystające wyspy, jakie można utworzyć z trójkątów o boku 1, i policzyć, ile ich jest.

Brzeg każdej wyspy, zbudowanej z co najwyżej dziesięciu trójkątów, jest łamaną zamkniętą złożoną z jednostkowych odcinków siatki i można go obiec (obrysować bez odrywania ołówka od papieru) w ten sposób, że dokładnie raz przebiegamy każdy odcinek brzegu i wracamy do punktu wyjścia. Może się zdarzyć, że trzeba będzie przy tym przejechać więcej niż raz przez ten sam punkt (patrz rysunek 2.4).

W przypadku wysp zbudowanych z co najwyżej dziesięciu trójkątów nie jest możliwa sytuacja taka, jak na rysunku 1.2, że brzeg figury składa się z dwóch rozłącznych części i nie można go obiec (obrysować bez odrywania ołówka od papieru).

Obiegając brzeg, po każdym jednostkowym odcinku wykonujemy skręt jednego z następujących typów:

• a - o 120 stopni w lewo,
• b - o 60 stopni w lewo,
• c - o 0 stopni (tzn. brak skrętu),
• d - o 60 stopni w prawo,
• e - o 120 stopni w prawo.

Każdy obieg brzegu wyspy można opisać za pomocą słowa złożonego z liter ze zbioru , odnotowując za pomocą odpowiedniej litery skręt, jaki należy wykonać po każdym kolejnym, jednostkowym odcinku łamanej tworzącej brzeg. Opis obiegu brzegu wyspy ma tyle liter, z ilu jednostkowych odcinków składa się łamana tworząca ten brzeg. Odnotowujemy skręt także po ostatnim odcinku łamanej, chociaż nie jest to konieczne dla jednoznacznego określenia jej kształtu. Ta, w pewnym sensie nadmiarowa, litera ułatwia przekształcenie danego opisu w opis innego obiegu tej samej figury, który zaczyna się w innym punkcie.

Słowa cdddcddd, dcdddcdd, cbbbcbbb opisują różne obiegi figury na rysunku 2.1.

Słowa cbeddcde, adcabcbb, abcbbadc opisują różne obiegi figury na rysunku 2.2.

Słowa acdabbcb i cddebced opisują różne obiegi figury na rysunku 2.3.

Jeśli obiegając brzeg wyspy mamy stale jej wnętrze po prawej stronie, to mówimy, że jest to obieg prawoskrętny.

Dla każdej wyspy można wyznaczyć zbiór wszystkich wysp do niej przystających oraz ich obiegi prawoskrętne. Kodem wyspy nazwiemy słowo, które:

1. jest opisem pewnego prawoskrętnego obiegu brzegu jakiejś wyspy do niej przystającej,
2. jest wcześniejsze w porządku alfabetycznym od wszystkich innych słów spełniających warunek 1.

Dla wysp przedstawionych na rysunkach 2.2 i 2.3, które są przystające, bierzemy pod uwagę wszystkie prawoskrętne obiegi obydwu:

beddcdec, eddcdecb, ddcdecbe, dcdecbed, cdecbedd, decbeddc, ecbeddcd, cbeddcde

oraz

bcedcdde, cedcddeb, edcddebc, dcddebce, cddebced, ddebcedc, debcedcd, ebcedcdd

i jako kod każdej z nich bierzemy to słowo, które w porządku alfabetycznym należy umieścić na pierwszym miejscu: bcedcdde.

Kodem wyspy przedstawionej na rysunku 2.4 jest słowo: aadecddcddde.

Napisz program, który:

• dla podanego kodu wyspy o rozmiarze wygeneruje kody wszystkich wysp o rozmiarze , które można utworzyć przez dodanie do niej jednego trójkąta,
• dla podanej liczby całkowitej wygeneruje kody wszystkich wysp rozmiaru .

Wejście

W pierwszym wierszu standardowego wejścia podana jest liczba całkowita (), oznaczająca liczbę zapytań. Każdy z kolejnych wierszy zawiera opis zapytania pewnego typu. Zapytanie typu 1 składa się z litery K oraz kodu wyspy składającej się z co najwyżej dziewięciu trójkątów, oddzielonych pojedynczym odstępem. Zapytanie typu 2 składa się z litery N oraz liczby całkowitej (), oddzielonych pojedynczym odstępem.

Wyjście

Na standardowe wyjście wypisz odpowiedzi dla poszczególnych zapytań.

Dla zapytań typu 1 należy najpierw wypisać liczbę różnych kodów wysp, które można utworzyć z przystających wysp opisanych podanym kodem poprzez dodanie jednego trójkąta. W następnym wierszu należy wypisać wszystkie te kody w kolejności alfabetycznej, pooddzielane pojedynczymi odstępami.

Dla zapytań typu 2 należy wypisać liczbę różnych kodów wysp utworzonych z trójkątów. W kolejnym wierszu należy wypisać wszystkie te kody w kolejności alfabetycznej.

Przykład

Dla danych wejściowych:

2
K adeccecced
N 5

poprawną odpowiedzią jest:

5
acedccecced addebcecced adebebecced adecbedcced cceccecce
4
aedddde bdecdde bececde ccedcde

Autor zadania: Andrzej Walat (zadanie z I Olimpiady Informatycznej).