Haskell , 228 227 225 224 bajtów
import Data.List
z=zipWith
a!b=div(max(a*a)(a*b))a
l x=z(!)(z(!)x(0:x))$tail x++[0]
s=(\x->length.($x).filter<$>[(>0),(<0)]).nub.(>>=id).(until=<<((==)=<<))((.)>>=id$transpose.map l).z(\i->z(\j x->2^i*j*(2*x-1))[1,3..])[1..]
Wypróbuj online!
Wyjaśnienie:
Pomysł na to rozwiązanie jest następujący: Zainicjuj macierz unikalnymi wartościami w każdej komórce, dodatnimi 1i ujemnymi dla 0. Następnie kilkakrotnie porównaj każdą komórkę z sąsiadami i, jeśli sąsiad ma ten sam znak, ale liczbę o większej wartości bezwzględnej, zamień numer komórki na numer sąsiada. Gdy osiągnie to ustalony punkt, policz liczbę odrębnych liczb dodatnich dla liczby 1regionów i wyraźnych liczb ujemnych dla liczby regionów0 regionów.
W kodzie:
s=(\x->length.($x).filter<$>[(>0),(<0)]).nub.(>>=id).(until=<<((==)=<<))((.)>>=id$transpose.map l).z(\i->z(\j x->2^i*j*(2*x-1))[1,3..])[1..]
można podzielić na przetwarzanie wstępne (przypisywanie liczb do komórek), iterację i przetwarzanie końcowe (zliczanie komórek)
Przetwarzanie wstępne
Część wstępnego przetwarzania jest funkcją
z(\i->z(\j x->2^i*j*(2*x-1))[1,3..])[1..]
Który używa zjako skrótu zipWithdo golenia kilku bajtów. To, co tu robimy, to spakowanie dwuwymiarowej tablicy z indeksami liczb całkowitych w wierszach i nieparzystymi indeksami liczb całkowitych w kolumnach. Robimy to, ponieważ możemy zbudować unikalną liczbę całkowitą z pary liczb całkowitych (i,j)przy użyciu formuły (2^i)*(2j+1). Jeśli generujemy tylko nieparzyste liczby całkowite j, możemy pominąć obliczanie 2*j+1, oszczędzając trzy bajty.
Dzięki unikalnemu numerowi musimy teraz tylko pomnożyć znak w oparciu o wartość w macierzy, która jest uzyskiwana jako 2*x-1
Iteracja
Iteracja jest wykonywana przez
(until=<<((==)=<<))((.)>>=id$transpose.map l)
Ponieważ dane wejściowe są w postaci listy list, przeprowadzamy porównanie sąsiadów w każdym wierszu, transponujemy macierz, ponownie wykonujemy porównanie w każdym wierszu (który ze względu na transpozycję było to, co było wcześniej w kolumnach) i transponujemy ponownie. Kod, który wykonuje jeden z tych kroków, to
((.)>>=id$transpose.map l)
gdzie ljest funkcja porównawcza (wyszczególniona poniżej) i transpose.map lwykonuje połowę kroków porównania i transpozycji. (.)>>=idwykonuje argument dwa razy, ponieważ \f -> f.fw tym przypadku jest on pozbawiony punktów i o jeden bajt krótszy ze względu na reguły pierwszeństwa operatora.
ljest zdefiniowany w powyższym wierszu jako l x=z(!)(z(!)x(0:x))$tail x++[0]. Ten kod wykonuje operator porównania (!)(patrz poniżej) na każdej komórce, najpierw z lewym sąsiadem, a następnie z prawym sąsiadem, poprzez skompresowanie listy xza pomocą listy przesuniętej w prawo 0:xi listy przesuniętej w lewotail x++[0] w lewo. Używamy zer do wypełniania przesuniętych list, ponieważ nigdy nie mogą wystąpić w macierzy wstępnie przetworzonej.
a!bjest zdefiniowany w wierszu powyżej tego jako a!b=div(max(a*a)(a*b))a. To, co chcemy tutaj zrobić, to następujące rozróżnienie wielkości liter:
- Jeśli
sgn(a) = -sgn(b)mamy dwa przeciwstawne obszary w macierzy i nie chcemy ich ujednolicać, więc apozostaje niezmienione
- Jeśli
sgn(b) = 0mamy skrzynkę narożną, w której bznajduje się wypełnienie, a zatem apozostaje niezmieniona
- Jeśli
sgn(a) = sgn(b)chcemy ujednolicić oba obszary i przyjąć ten o większej wartości bezwzględnej (dla wygody).
Zauważ, że sgn(a)nigdy nie będzie 0. Osiągamy to dzięki podanej formule. Jeśli znaki ai bróżnią się, a*bjest mniejsze lub równe zero, a a*azawsze jest większe od zera, więc wybieramy je jako maksimum i dzielimy z, aaby wrócić a. W przeciwnym razie max(a*a)(a*b)jest abs(a)*max(abs(a),(abs(b))i dzieląc to przeza , otrzymujemy sgn(a)*max(abs(a),abs(b)), co jest liczbą o większej wartości bezwzględnej.
Aby iterować funkcję, ((.)>>=id$transpose.map l)dopóki nie osiągnie ustalonego punktu, używamy (until=<<((==)=<<)), który jest wzięty z tej odpowiedzi przepełnienia stosu .
Przetwarzanie końcowe
Do przetwarzania końcowego używamy tej części
(\x->length.($x).filter<$>[(>0),(<0)]).nub.(>>=id)
który jest tylko zbiorem kroków.
(>>=id)zgniata listę list w jedną listę,
nubpozbywa się dubletów,
(\x->length.($x).filter<$>[(>0),(<0)])dzieli listę na parę list, jedną na liczby dodatnie i jedną na liczby ujemne, i oblicza ich długości.
[[1,0];[0,1]]