Biorąc pod uwagę niepustą tablicę 2D składającą się z 0i 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 .

JavaScript (ES6), 127 124 119 bajtów

Zaoszczędzono 3 bajty dzięki nderscore

m=>(F=(x,y)=>m.map((r,Y)=>r.map((i,X)=>i?1/y?n+=x<X&y<=Y&(g=(a,b)=>(m[b+X-x]||0)[a-Y+y])(x,y)&g(X,Y):F(X,Y):0)))(n=0)|n

W jaki sposób?

Ta funkcja wykonuje iterację na wszystkich parach komórek (x, y) , (X, Y) macierzy wejściowej m, tak że:

• m [x, y] = m [X, Y] = 1
• x <X
• y ≤ Y

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

let f =

m=>(F=(x,y)=>m.map((r,Y)=>r.map((i,X)=>i?1/y?n+=x<X&y<=Y&(g=(a,b)=>(m[b+X-x]||0)[a-Y+y])(x,y)&g(X,Y):F(X,Y):0)))(n=0)|n

console.log(f([
  [0,0,0,1,0,0,0],
  [1,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,1,0,0],
  [0,1,0,0,0,0,0]
]));

console.log(f([
  [1,0,1,0,1],
  [0,0,0,0,0],
  [1,0,1,0,0],
  [0,0,0,0,0],
  [1,0,0,0,1]
]));

console.log(f([
  [1,1,1,1],
  [1,1,1,1],
  [1,1,1,1],
  [1,1,1,1]
]));

MATL , 20 bajtów

&fJ*+4XN!"@&-|un3=vs

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):

&f      % Input (implicit). Push vectors of row and column indices of nonzero entries
J*      % Multiply by imaginary unit
+       % Add the two vectors. Gives a vector of complex coordinates
4XN     % Matrix of combinations of these complex numbers, taken 4 at a time. Each
        % row is a combination
!       % Transpose
"       % For each column
  @     %   Push current column: candidate set of four points
  &-    %   All pair-wise differences
  |     %   Absolute value
  u     %   Unique entries
  n3=   %   Does the number of elements equal 3? Gives true (1) or false (0)
  vs    %   Concatenate vertically with previous accumulated result, and sum
        % End (implicit). Display (implicit)