Encontre o número de retângulos em uma matriz de bytes 2D

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

Você recebe uma matriz bidimensional de bytes do tamanho mx n. É garantido que todos os bytes sejam 1 ou 0. Encontre o número de retângulos representados por 1s quando visualizados em 2d, como mostrado acima.

Somente retângulos totalmente preenchidos são considerados para a contagem.
Os retângulos devem ser cercados por zeros, a menos que estejam na borda (os retângulos que tocam na diagonal dos zeros são válidos (veja o exemplo)).

Por exemplo, na matriz acima, existem 5 retângulos válidos.

Você pode usar qualquer idioma.

popularity-contest microbiano
fonte
1
Eu acho que a melhor maneira de dizer isso é dizer: retângulos devem ser cercados por
zeros
Feito. Obrigado por redigir em um inglês melhor.
microbian
Que tal 1100\n1100\n0011\n0011?
Cruncher
1
Eu acho que foi por isso que escrevi 'adjacente / sobreposto'. Estes são 2 retângulos válidos da minha intenção inicial. Mas a condição 'circundante' os está restringindo agora. Você tem uma maneira melhor de explicar isso
Microbian
1
Mesmo em adjacentes, é ambíguo se diagonal significa ou não adjacente. A mesma ambigüidade ou não meios cercado, cercado nos cantos ou lados apenas
Cruncher

Respostas:

2

GolfScript, 107 caracteres

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

A entrada deve ser fornecida no STDIN.

Exemplos:

11
01
-
0

111
111
-
1

100
001
001
-
2

11100
10101
11100
-
1

101
010
101
-
5
Howard
fonte
Veja os comentários acima - parece que retângulos "válidos" precisam ter largura / altura ambos> 1.
Paul R
@PaulR Essa regra não está escrita na pergunta; por todas as definições razoáveis, esses são retângulos perfeitamente finos - talvez eu acrescente isso mais tarde.
Howard
Concordo com a sua definição - eu estava apenas observando a discrepância nos comentários - parece que o OP precisa atualizar a pergunta para torná-la mais definitiva.
Paul R
Esclareci que o retângulo de tamanho 1 é válido.
microbian
Mas você também disse nos comentários, em resposta a: "Apenas para esclarecimento, os retângulos degenerados não devem ser contados, correto? Por exemplo, um único 1 ou uma sub-coluna / subcoluna de 1 adjacente é inválido?" dizendo: "Sim, eles são inválidos e não devem ser contados".
Paul R