Finden Sie die Anzahl der Rechtecke in einem 2D-Byte-Array

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

Sie erhalten ein zweidimensionales Array von Bytes der Größe mx n. Es ist garantiert, dass alle Bytes Einsen oder Nullen sind. Ermitteln Sie die Anzahl der durch Einsen dargestellten Rechtecke in 2d, wie oben gezeigt.

Zum Zählen werden nur vollständig ausgefüllte Rechtecke berücksichtigt.
Rechtecke müssen von Nullen umgeben sein, es sei denn, sie befinden sich an der Kante (die diagonal berührenden Rechtecke von 1 sind jedoch in Ordnung (siehe Beispiel)).

Zum Beispiel gibt es in dem obigen Array 5 gültige Rechtecke.

Sie können eine beliebige Sprache verwenden.

popularity-contest mikrobisch
quelle
1
Ich denke, eine bessere Art zu sagen ist: Rechtecke müssen von
Nullen
Erledigt. Vielen Dank für die Formulierung in einem besseren Englisch.
Mikrobier
Was ist 1100\n1100\n0011\n0011?
Cruncher
1
Ich denke, deshalb habe ich 'angrenzend / überlappend' geschrieben. Dies sind 2 gültige Rechtecke aus meiner ursprünglichen Absicht. Aber die 'umgebende' Bedingung schränkt sie jetzt ein. Haben Sie einen besseren Weg, um es zu erklären
Mikrobier
1
Sogar bei benachbarten ist es nicht eindeutig, ob diagonal benachbart bedeutet oder nicht. Die gleiche Mehrdeutigkeit, ob umgeben oder nicht, bedeutet, an den Ecken oder nur an den Seiten umgeben
Cruncher

Antworten:

2

GolfScript, 107 Zeichen

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

Die Eingabe muss auf STDIN erfolgen.

Beispiele:

11
01
-
0

111
111
-
1

100
001
001
-
2

11100
10101
11100
-
1

101
010
101
-
5
Howard
quelle
Siehe Kommentare oben - es scheint, dass "gültige" Rechtecke Breite / Höhe> 1 haben müssen.
Paul R
@PaulR Diese Regel steht nicht in der Frage, nach allen vernünftigen Definitionen sind das vollkommen feine Rechtecke - vielleicht füge ich das später hinzu.
Howard
Ich stimme Ihrer Definition zu - ich habe nur die Diskrepanz in den Kommentaren bemerkt - es sieht so aus, als müsste OP die Frage aktualisieren, um sie endgültiger zu machen.
Paul R
Ich habe klargestellt, dass ein Rechteck der Größe 1 gültig ist.
Mikrobier
Sie sagten aber auch in den Kommentaren zu: "Nur zur Verdeutlichung sollten entartete Rechtecke nicht gezählt werden, richtig? Sind beispielsweise eine einzelne 1 oder eine einzelne Unterzeile / Unterspalte der benachbarten 1 ungültig?" mit den Worten: "Ja, sie sind ungültig und sollten nicht gezählt werden."
Paul R