Biorąc pod uwagę niepustą tablicę 2D składającą się z 0
i 1
, znajdź liczbę kwadratów, których wszystkie 4 rogi są wszystkie 1
. Kwadraty nie muszą być „pionowe”. Wszystkie rzędy mają taką samą długość.
Dozwolone są rozsądne metody wejścia / wyjścia.
Przypadki testowe:
0001000
1000000
0000000
0000100
0100000
To zwraca 1
.
10101
00000
10100
00000
10001
To zwraca 2
.
1111
1111
1111
1111
To zwraca 20
.
To jest golf golfowy . Najkrótsza odpowiedź w bajtach wygrywa. Obowiązują standardowe luki .
1
s na kwadracie, tak że każda z nich1
jest w równej odległości wzdłuż obwodu od dwóch sąsiadów.Odpowiedzi:
JavaScript (ES6),
127124119 bajtówZaoszczędzono 3 bajty dzięki nderscore
W jaki sposób?
Ta funkcja wykonuje iterację na wszystkich parach komórek (x, y) , (X, Y) macierzy wejściowej m, tak że:
Każda pasująca para opisuje współrzędne potencjalnej krawędzi kwadratu. Nierówności gwarantują, że każda krawędź jest testowana tylko raz.
Używamy wektora [dx, dy] = [X - x, Y - y] obróconego o 90 ° zgodnie z ruchem wskazówek zegara, aby przetestować komórki znajdujące się w [x - dy, y + dx] i [X - dy, Y + dx] . Jeśli oba zawierają 1 , znaleźliśmy prawidłowy kwadrat.
Przypadki testowe
Pokaż fragment kodu
źródło
g=(a,b)=>(m[b+X-x]||0)[a-Y+y]
-1 bajt: użyj|n
zamiast&&n
MATL , 20 bajtów
Dane wejściowe to macierz.
Wypróbuj online!
Jak to działa
Znajduje wszystkie współrzędne niezerowych wpisów w siatce wprowadzania i reprezentuje je jako liczby zespolone, tak że indeksy wierszy i kolumn odpowiadają odpowiednio części rzeczywistej i urojonej.
Następnie kod generuje tablicę wszystkich kombinacji (kolejność nie ma znaczenia) z tych liczb wziętych 4 na raz. Każda kombinacja reprezentuje kwadrat kandydujący. Dla każdej kombinacji obliczana jest macierz 4 × 4 par bezwzględnych różnic (tj. Odległości w płaszczyźnie zespolonej). Jest to macierz symetryczna z zerami wzdłuż głównej przekątnej. Obecna kombinacja tworzy kwadrat wtedy i tylko wtedy, gdy macierz zawiera dokładnie 3 różne wartości (będą to strona kwadratowa, kwadratowa przekątna i zero):
Z drugiej strony, na przykład, niekwadratowy prostokąt dałby 4 różne wartości (dwie strony, jedna wartość po przekątnej i zero);
a ogólny czworokąt może mieć do 7 wartości (cztery boki, dwie przekątne i zero):
źródło