Cuente el número de "agujeros" en un mapa de bits

Question

Considere un mapa de bits MxN donde las celdas son 0 o 1. '1' significa llenado y '0' significa vacío.

Encuentra el número de 'agujeros' en el mapa de bits, donde un agujero es una región contigua de celdas vacías.

Por ejemplo, esto tiene dos agujeros:

11111 
10101 
10101 
11111 

... y esto tiene una sola:

11111 
10001 
10101 
11111 

¿Cuál es la manera más rápida, cuando M y N son a la vez entre 1 y 8?

Aclaración: diagonales no se consideran contiguas, sólo importa lado de adyacencia.

Nota: Estoy buscando algo que toma ventaja del formato de datos. Sé cómo transformar esto en un gráfico y [BD] FS, pero eso parece excesivo.

Answer 1

Necesita hacer connected component labeling en su imagen. Puede usar el Two-pass algorithm descrito en el artículo de Wikipedia que he vinculado anteriormente. Dado el pequeño tamaño de su problema, el One-pass algorithm puede ser suficiente.

También podría usar BFS/DFS pero yo recomendaría los algoritmos anteriores.

Answer 2

Esto parece un buen uso de la estructura de datos disjuntos.
convertir el mapa de bits en una matriz 2D
bucle a través de cada elemento
si el elemento actual es un 0, fusionarlo con el conjunto de uno de sus vecinos vacíos "anteriores (ya visitados)
si no tiene vecinos vacíos , añadirlo a su propio conjunto

luego simplemente contar el número de conjuntos

Answer 3

puede haber ventajas que se obtienen mediante el uso de búsquedas en tablas y operaciones bit a bit.

Por ejemplo, puede buscarse una línea completa de 8 píxeles en la tabla de 256 elementos, por lo que el número de agujeros en un campo 1xN se obtiene mediante búsqueda simple. Entonces puede haber alguna tabla de búsqueda de elementos 256xK, donde K es el número de configuraciones de agujeros en la línea anterior, contando el número de agujeros completos y la configuración del próximo agujero. Esa es solo una idea.