Étant donné un tableau 2D non vide composé de 0et 1, trouvez le nombre de carrés dont les 4 coins sont tous 1. Les carrés n'ont pas besoin d'être "droits". Toutes les rangées sont garanties d'avoir la même longueur.

Des méthodes d'entrée / sortie raisonnables sont autorisées.

Testcases:

0001000
1000000
0000000
0000100
0100000

Cela revient 1.

10101
00000
10100
00000
10001

Cela revient 2.

1111
1111
1111
1111

Cela revient 20.

C'est du code-golf . La réponse la plus courte en octets l'emporte. Des échappatoires standard s'appliquent.

JavaScript (ES6), 127 124 119 octets

Sauvegardé 3 octets grâce à 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

Comment?

Cette fonction itère sur toutes les paires de cellules (x, y) , (X, Y) de la matrice d'entrée m telles que:

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

Chaque paire correspondante décrit les coordonnées d'un bord potentiel d'un carré. Les inéquations garantissent que chaque arête n'est testée qu'une seule fois.

Nous utilisons le vecteur [dx, dy] = [X - x, Y - y] tourné de 90 ° dans le sens horaire pour tester les cellules situées à [x - dy, y + dx] et [X - dy, Y + dx] . S'ils contiennent tous les deux un 1 , nous avons trouvé un carré valide.

Cas de test

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 octets

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

L'entrée est une matrice.

Essayez-le en ligne!

Comment ça fonctionne

Cela trouve toutes les coordonnées des entrées non nulles dans la grille d'entrée et les représente sous forme de nombres complexes, de sorte que les indices de ligne et de colonne correspondent respectivement aux parties réelles et imaginaires.

Le code génère ensuite un tableau de toutes les combinaisons (l'ordre n'a pas d'importance) de ces nombres pris 4 à la fois. Chaque combinaison représente un carré candidat. Pour chaque combinaison, la matrice 4 × 4 des différences absolues par paire (c'est-à-dire les distances dans le plan complexe) est calculée. Il s'agit d'une matrice symétrique avec des zéros le long de sa diagonale principale. La combinaison actuelle forme un carré si et seulement si la matrice contient exactement 3 valeurs distinctes (ce seront le côté carré, la diagonale carrée et zéro):

Par contre, par exemple, un rectangle non carré donnerait lieu à 4 valeurs distinctes (deux côtés, une valeur diagonale et zéro);

et un quadrilatère général peut avoir jusqu'à 7 valeurs (quatre côtés, deux diagonales et zéro):

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