Besteht ein nicht leeres 2D-Array aus 0und 1, ermitteln Sie die Anzahl der Quadrate, deren 4 Ecken alle sind 1. Die Quadrate müssen nicht "aufrecht" sein. Alle Reihen haben garantiert die gleiche Länge.

Angemessene Eingabe- / Ausgabemethoden sind zulässig.

Testfälle:

0001000
1000000
0000000
0000100
0100000

Dies kehrt zurück 1.

10101
00000
10100
00000
10001

Dies kehrt zurück 2.

1111
1111
1111
1111

Dies kehrt zurück 20.

Das ist Code-Golf . Kürzeste Antwort in Bytes gewinnt. Es gelten Standardlücken .

JavaScript (ES6), 127 124 119 Byte

Dank nderscore 3 Bytes gespart

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

Wie?

Diese Funktion durchläuft alle Paare von Zellen (x, y) , (X, Y) der Eingabematrix m, so dass:

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

Jedes übereinstimmende Paar beschreibt die Koordinaten einer potenziellen Kante eines Quadrats. Die Ungleichungen garantieren, dass jede Kante nur einmal geprüft wird.

Wir verwenden den um 90 ° im Uhrzeigersinn gedrehten Vektor [dx, dy] = [X - x, Y - y], um die Zellen zu testen, die sich bei [x - dy, y + dx] und [X - dy, Y + dx] befinden . Wenn beide eine 1 enthalten , haben wir ein gültiges Quadrat gefunden.

Testfälle

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 Bytes

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

Eingabe ist eine Matrix.

Probieren Sie es online!

Wie es funktioniert

Dadurch werden alle Koordinaten von Nicht-Null-Einträgen im Eingaberaster gefunden und als komplexe Zahlen dargestellt, sodass Zeilen- und Spaltenindizes Real- bzw. Imaginärteilen entsprechen.

Der Code generiert dann ein Array aller Kombinationen (Reihenfolge spielt keine Rolle) dieser Zahlen, die jeweils zu 4 verwendet werden. Jede Kombination repräsentiert ein Kandidatenquadrat. Für jede Kombination wird die 4 × 4-Matrix paarweiser absoluter Differenzen (dh Abstände in der komplexen Ebene) berechnet. Dies ist eine symmetrische Matrix mit Nullen entlang ihrer Hauptdiagonale. Die aktuelle Kombination bildet genau dann ein Quadrat, wenn die Matrix genau drei unterschiedliche Werte enthält (dies sind die Quadratseite, die Quadratseite und die Null):

Andererseits würde beispielsweise ein nicht quadratisches Rechteck 4 unterschiedliche Werte ergeben (zwei Seiten, eine Diagonale und Null);

und ein allgemeines Viereck kann bis zu 7 Werte haben (vier Seiten, zwei Diagonalen und Null):

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