Znajdź liczbę prostokątów w tablicy bajtów 2D

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

Otrzymujesz 2-wymiarową tablicę bajtów o rozmiarze mx n. Gwarantujemy, że wszystkie bajty to 1 lub 0. Znajdź liczbę prostokątów reprezentowanych przez 1 w widoku 2d, jak pokazano powyżej.

Do zliczania brane są pod uwagę tylko w pełni wypełnione prostokąty.
Prostokąty muszą być otoczone zerami, chyba że znajdują się na krawędzi (prostokąty 1 dotykające ukośne są w porządku (patrz przykład.)).

Na przykład w powyższej tablicy znajduje się 5 prawidłowych prostokątów.

Możesz używać dowolnego języka.

popularity-contest drobnoustrój
źródło
1
Myślę, że lepszym sposobem na wyrażenie tego jest powiedzenie: prostokąty muszą być otoczone
zerami
Gotowy. Dzięki za sformułowanie go w lepszym angielskim.
mikrobiolog
Co 1100\n1100\n0011\n0011?
Cruncher
1
Myślę, że dlatego napisałem „sąsiadujące / nakładające się”. Są to 2 prawidłowe prostokąty z mojej pierwotnej intencji. Ale warunki „otaczające” je teraz ograniczają. Czy masz lepszy sposób, aby to wyjaśnić
mikrobian
1
Nawet w sąsiedztwie nie jest jednoznaczne, czy przekątna oznacza sąsiedztwo, czy nie. Ta sama dwuznaczność, niezależnie od tego, czy jest otoczona, czy też nie, oznacza w narożnikach lub po bokach
Cruncher

Odpowiedzi:

2

GolfScript, 107 znaków

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

Dane wejściowe należy podać na STDIN.

Przykłady:

11
01
-
0

111
111
-
1

100
001
001
-
2

11100
10101
11100
-
1

101
010
101
-
5
Howard
źródło
Patrz komentarze powyżej - wydaje się, że „prawidłowe” prostokąty muszą mieć szerokość / wysokość zarówno> 1.
Paul R
@PaulR Ta zasada nie jest zapisana w pytaniu, przy wszystkich rozsądnych definicjach są to idealnie drobne prostokąty - może dodam to później.
Howard
Zgadzam się z twoją definicją - właśnie zauważyłem rozbieżność w komentarzach - wygląda na to, że OP musi zaktualizować pytanie, aby było bardziej ostateczne.
Paul R
Wyjaśniłem, że prostokąt o rozmiarze 1 jest prawidłowy.
mikrobiolog
Ale powiedziałeś również w komentarzach w odpowiedzi na: „Dla wyjaśnienia, zdegenerowane prostokąty nie powinny być liczone, prawda? Na przykład, czy jeden 1 lub pojedynczy subrow / subkolumna sąsiednich 1 jest nieważna?” mówiąc: „Tak, są one nieważne i nie należy ich liczyć”.
Paul R