Contando islas en matrices booleanas

9

Dado un matriz booleana , dejemos que entradas representen el mar y entradas representen la tierra. Definir una isla como (pero no en diagonal) vertical u horizontalmente adyacentes entradas.n×mX011

La pregunta original era contar el número de islas en una matriz dada. El autor describió una solución recursiva ( memoria).O(nm)

Pero estaba intentando sin éxito encontrar una solución de transmisión (de izquierda a derecha, y luego hacia la fila siguiente) que cuenta dinámicamente las islas con o o memoria (no hay límites para la complejidad del tiempo). ¿Es eso posible? Si no, ¿cómo puedo probarlo?O(m)O(n)O(n+m)


Algunos ejemplos de salidas esperadas para ciertas entradas para la countfunción:

count(010111010)=1;count(101010101)=5;count(111101111)=1;

count(1111100100010110100011011111)=2

count(101111)=1

pgs
fuente
1
1. ¿Qué quieres decir con "ortogonal"? ¿Te refieres a un componente conectado? 2. ¿Qué podemos suponer acerca de cómo se almacena la matriz? ¿Podemos suponer que está almacenado en un almacenamiento externo (por ejemplo, un disco duro lento), para que pueda leer cualquier parte que desee, pero será más rápido leerlo un bloque a la vez? ¿O recibimos la matriz de una manera de transmisión, donde una vez que hemos recibido un poco de la matriz de entrada, nunca más podemos ver ese bit de entrada?
DW
1
Genial, gracias. Te animo a editar la pregunta para aclarar esos puntos. Si se está transmitiendo, ¿en qué orden llegan los bits de la matriz? ¿Escaneando de izquierda a derecha entre una fila y luego hacia la siguiente fila?
DW
1
Edite la pregunta para incluir todos estos detalles. Los comentarios son efímeros.
Yuval Filmus
2
No toda la información dada en los comentarios se puede encontrar en la publicación misma. Parte de esta información es bastante crucial, como su modelo de transmisión. Los comentarios podrían desaparecer, y así (y debido a los estándares de la comunidad), todos los detalles necesarios deberían formar parte de la publicación principal.
Yuval Filmus
1
¿Cuál es la complejidad de tiempo requerida?
hengxin

Respuestas:

4

Aquí hay un boceto de un algoritmo que solo mantiene dos filas en la memoria a la vez, por lo que memoria. Pero como puede ejecutar este algoritmo en la transposición de la matriz sin problemas, la complejidad real es la memoria O ( min ( m , n ) ) . El tiempo de procesamiento es O ( m n ) .O(m)O(min(m,n))O(mn)

  1. Inicializacion. Escanee sobre la primera fila y encuentre todas las subcadenas conectadas de esa fila. Asigne a cada subcadena disjunta una identificación positiva única y guárdela como un vector que es cero donde es cero y la identificación positiva única de lo contrario.X

  2. Para cada fila restante, asigne identificadores únicos (nunca reasigne identificadores únicos anteriores, asegúrese de que sus identificadores estén aumentando estrictamente) a las subcadenas en esa fila nuevamente. Vea la fila anterior más la fila actual como una matriz de por m , y cualquier área conectada debe asignarse a su mínimo. Como ejemplo:2m

    010402220333300506607080009990010402220333300504402020003330

    No es necesario actualizar la fila anterior para la corrección de este algoritmo, solo la actual.

    Una vez hecho esto, busque el conjunto de todos los identificadores en la fila anterior que no se conectan a la siguiente fila, descartando duplicados . Agregue el tamaño de este conjunto a su contador de islas en ejecución.

    Ahora puede descartar la fila anterior y asignar la fila actual a la fila anterior y continuar.

  3. Para manejar correctamente la última fila, finja que hay otra fila de ceros en la parte inferior de y ejecute el paso 2 nuevamente.X

orlp
fuente
6

Orlp ofrece una solución utilizando palabras de espacio, que son O ( n log n ) bits de espacio (suponiendo, por simplicidad, que n = m ). Por el contrario, es fácil demostrar que se necesitan Ω ( n ) bits de espacio al reducir la desunión establecida a su problema.O(n)O(nlogn)n=mΩ(n)

x1,,xny1,,ynixi=yi=12×(2n1)x1,0,x2,0,,0,xny1,0,y2,0,,0,ynixii(xi+yi)iΩ(n)Ω(n)

O(n)O(logn)O(n)

Yuval Filmus
fuente