Encuentra el número de rectángulos en una 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

Se le proporciona una matriz bidimensional de bytes de tamaño mx n. Se garantiza que todos los bytes son 1 o 0. Encuentre el número de rectángulos representados por 1 cuando se ve en 2d, como se muestra arriba.

Solo los rectángulos completamente rellenos se consideran para contar.
Los rectángulos deben estar rodeados por 0 a menos que estén en el borde (los rectángulos que tocan diagonalmente 1 están bien, sin embargo (ver ejemplo)).

Por ejemplo, en la matriz anterior hay 5 rectángulos válidos.

Puedes usar cualquier idioma.

microbiano
fuente
1
Creo que una mejor manera de expresarlo es decir que: los rectángulos deben estar rodeados por
ceros
Hecho. Gracias por redactarlo en un mejor inglés.
microbio
¿Qué hay de 1100\n1100\n0011\n0011?
Cruncher
1
Creo que por eso escribí 'adyacente / superpuesto'. Estos son 2 rectángulos válidos de mi intención inicial. Pero la condición 'circundante' los está restringiendo ahora. ¿Tiene una mejor manera de explicarlo
Microbian
1
Incluso en adyacente es ambiguo si diagonal significa adyacente o no. La misma ambigüedad, ya sea rodeada o no, significa, rodeada en las esquinas o solo a los lados
Cruncher

Respuestas:

2

GolfScript, 107 caracteres

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

La entrada debe darse en STDIN.

Ejemplos:

11
01
-
0

111
111
-
1

100
001
001
-
2

11100
10101
11100
-
1

101
010
101
-
5
Howard
fuente
Vea los comentarios anteriores: parece que los rectángulos "válidos" deben tener ancho / alto ambos> 1.
Paul R
@PaulR Esa regla no está escrita en la pregunta, según todas las definiciones razonables, esos son rectángulos perfectamente finos, tal vez lo agregaré más tarde.
Howard
Estoy de acuerdo con su definición, solo noté la discrepancia en los comentarios, parece que OP necesita actualizar la pregunta para que sea más definitiva.
Paul R
Aclaré que el rectángulo de tamaño 1 es válido.
microbio
Pero también dijo en los comentarios, en respuesta a: "Solo para aclarar, los rectángulos degenerados no deberían contarse, ¿correcto? Por ejemplo, ¿un solo 1 o una subcuenta / subcolumna de 1 adyacente no es válido?" diciendo: "Sí, no son válidos y no deben contarse".
Paul R