Powinieneś napisać program lub funkcję, która odbiera ciąg opisujący podłogę jako dane wejściowe i wyjściowe lub zwraca obszar najprostszego metapłytki, który mógłby stworzyć dany wzór podłogi.
Podłoga jest częścią kwadratowej siatki. Każda kwadratowa płytka ma kolor lazurowy lub czarny (reprezentowany przez a
i b
na wejściu).
Przykładowa podłoga:
aaaa
ababab
aaaaa
Meta-płytki
- zbudowana jest ze związku
N
oM
prostokątnym meta-dachówki lazur i czarne kwadraty - używane metapłytki są identyczne do tłumaczenia (nie można ich obracać ani kopiować)
- jeśli boki dwóch metapłytek są połączone, powinny łączyć się na całej długości (tj. metapłytki kafelkami przestrzeń w sposób podobny do siatki)
Przykładowy metapłytek:
ba
aa
i utworzony przez niego metapłytek:
.
.
.
babababa
aaaaaaaa
... babababa ...
aaaaaaaa
babababa
aaaaaaaa
.
.
.
Ten metapłytek tworzy pokazaną górną podłogę, ponieważ lewe litery pokazują:
.
.
.
********
***aaaa*
... *ababab* ...
*aaaaa**
********
********
.
.
.
Metapłytek jest prostszy niż inny, jeśli powierzchnia jego metapłytki jest mniejsza. Nasz przykład ma powierzchnię, 2*2 = 4
która jest najmniejszą możliwą dla przykładowej podłogi. Wynik powinien być 4
na przykład.
Wejście
- Ciąg składający się ze znaków
a b space
inewline
zawierający co najmniej jedena
lubb
. - Litery (
ab
) tworzą jeden 4-połączony (połączony obok siebie) kształt. - Z przodu wierszy nie będzie niepotrzebnych miejsc, tzn. Co najmniej jeden rząd będzie zaczynać się od
a
lubb
. Możesz wybrać dwa formaty wejściowe:
- Brak niepotrzebnych białych znaków na końcu wierszy (jak pokazano w przykładach).
- Odstępy po prawej stronie rzędów, aby wszystkie rzędy miały taką samą długość jak najdłuższy rząd.
Końcowy znak nowej linii jest opcjonalny.
Wynik
- Pojedyncza liczba całkowita, obszar najmniejszej możliwej metapłytki, której kafelki zawierają podłogę wejściową.
Przykłady
Przykłady są rozdzielane myślnikami. Trzy części przykładu to wejście, wyjście i jedna z najmniejszych możliwych metapłytek.
a
1
a
-----------------
aaaa
aaa
a
1
a
-----------------
aabaab
abaa
aaba
6
aab
aba
-----------------
aabaab
a a a
aabab
18
aabaab
aaaaaa
aababa
-----------------
ba
aaab
8
baaa
aaab
-----------------
aaaa
ababb
aaaa
10
aaaaa
ababb
-----------------
a aa
ab ba
aba
6
aa
ab
ba
-----------------
aaaa
abab
aaaa
4
aa
ab
-----------------
ba
ba
b
4
ba
ab
-----------------
baa
aba
aab
9
baa
aba
aab
-----------------
aaaa
aabaa
aaaa
6
aaa
aab
To jest golf golfowy, więc wygrywa najkrótszy wpis.
Odpowiedzi:
C - 208 bajtów
Kod ekwiwalentny przed golfem:
Algorytm jest dość brutalny, więc powinno być dość oczywiste, jak działa na podstawie kodu. Oto kilka komentarzy:
q
. Wychodzi zreturn
meta-płytką, która może pokryć podłogę. Zauważ, że pętla nie potrzebuje innego warunku wyjścia, ponieważ zawsze istnieje rozwiązanie (najgorszym przypadkiem jest rozmiar danych wejściowych).if
wylicza prawidłowe kombinacje szerokości / wysokości metapłytki dla rozmiaruq
.u
to indeks meta płytki, który odpowiada kafelkowi podłogi.a
lub sąb
różne (sumaa = 97
ib = 98
jest195
), występuje niezgodność, a rozmiar metapłytki z próbowanymi wymiarami nie będzie działać.a
lubb
, kolor płytki jest kopiowany do kandydującej metapłytki.Zastosowany kod testowy:
Wynik:
źródło