Trouver le nombre de rectangles dans un tableau d'octets 2D

12 
0000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000001111111111111100000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000011111100000000000000000000011111111111111100000000000000000
0000000000011111100000000000000000000011111111111111100000000000000000
0000000000011111100000000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000000000000000000000000000000011111111111111100000000000000000
0000000000000111111000000000000000000011111111111111100000000000000000
0000000000000100001000000111111000000011111111111111100000000010000000
0000000000000100001000000111111000000000000000000000011000000000000000
0000000000000111111000000111111000000000000000000000011000000000000000
0000000000000000000000000000111111000000000000000000000000000000000000
0000000000000000000000000000111111000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000

On vous donne un tableau bidimensionnel d'octets de taille mx n. Il est garanti que tous les octets sont à 1 ou à 0. Trouvez le nombre de rectangles représentés par des 1 lorsqu'ils sont affichés en 2D, comme indiqué ci-dessus.

Seuls les rectangles entièrement remplis sont pris en compte pour le comptage.
Les rectangles doivent être entourés de 0 à moins qu'ils ne soient sur le bord (les rectangles se touchant en diagonale sont bien cependant (voir l'exemple.)).

Par exemple, dans le tableau ci-dessus, il y a 5 rectangles valides.

Vous pouvez utiliser n'importe quelle langue.

popularity-contest microbien
la source
1
Je pense qu'une meilleure façon de le dire est de dire que: les rectangles doivent être entourés de 0 ou d'un bord
Cruncher
Terminé. Merci de l'avoir rédigé dans un meilleur anglais.
microbian
Et alors 1100\n1100\n0011\n0011?
Cruncher
1
Je pense que c'est pourquoi j'ai écrit «adjacent / chevauchant». Ce sont 2 rectangles valides de mon intention initiale. Mais la condition «environnante» les restreint maintenant. Avez-vous une meilleure façon de l'expliquer
microbian
1
Même à côté, il est ambigu que diagonale signifie adjacent ou non. La même ambiguïté, entourée ou non, signifie entourée dans les coins ou juste sur les côtés
Cruncher

Réponses:

2

GolfScript, 107 caractères

.n?):L;'1'/{,}%{1$+)}*;][]\{:A{{+}+[1L.~)-1]%&}+1$\,.@^\[[[A]]+{|}*]+}/{.{L%}{%$..&1$,1$,/*$=}:C~\{L/}C&},,

L'entrée doit être donnée sur STDIN.

Exemples:

11
01
-
0

111
111
-
1

100
001
001
-
2

11100
10101
11100
-
1

101
010
101
-
5
Howard
la source
Voir les commentaires ci-dessus - il semble que les rectangles "valides" doivent avoir une largeur / hauteur à la fois> 1.
Paul R
@PaulR Cette règle n'est pas écrite dans la question, selon toutes les définitions raisonnables, ce sont des rectangles parfaitement fins - j'ajouterai peut-être cela plus tard.
Howard
Je suis d'accord avec votre définition - je notais simplement la différence dans les commentaires - il semble que OP doive mettre à jour la question pour la rendre plus définitive.
Paul R
J'ai précisé que le rectangle de taille 1 est valide.
microbian
Mais vous avez également dit dans les commentaires, en réponse à: "Juste pour plus de précision, les rectangles dégénérés ne devraient pas être comptés, correct? Par exemple, un seul 1 ou une seule sous-ligne / sous-colonne de 1 adjacent est-elle invalide?" en disant: "Oui, ils sont invalides et ne doivent pas être comptés".
Paul R