algorithm - para - ¿Cómo puedo encontrar el agujero en una matriz 2D?
multiplicacion matriz c# (5)
Cree algún tipo de clase "LinkedCells" que almacene celdas que estén vinculadas entre sí. Luego, marque las celdas una por una en el orden de izquierda a derecha y de arriba a abajo, realizando las siguientes comprobaciones para cada celda: si la celda adyacente es negra, agregue esta celda al grupo de esa celda. De lo contrario, debe crear un nuevo grupo para esta celda. Solo debes comprobar si hay vecino superior e izquierdo.
UPD: Lo siento, me olvidé de fusionar grupos: si las dos celdas vecinas son negras y pertenecen a grupos diferentes, debes unificar los grupos en uno.
Su clase "LinkedCells" debe tener una bandera si está conectada al borde. Es falso por defecto y se puede cambiar a verdadero si agrega una celda de borde a este grupo. En caso de fusionar dos grupos, debe establecer una nueva bandera como || de banderas anteriores. Al final, tendrá un conjunto de grupos y cada grupo que tenga una bandera de conexión falsa será "agujero".
Este algoritmo será O (x * y).
Sé que el título parece algo ambiguo y por esta razón he adjuntado una imagen que será útil para entender el problema con claridad. Necesito encontrar agujeros dentro de la región blanca. Un agujero se define como una o varias celdas con un valor ''0'' dentro de la región blanca. Quiero decir que tendrá que estar completamente encerrado por celdas con un valor ''1'' (por ejemplo, aquí podemos ver tres agujeros marcados como 1, 2 y 3 ). Se me ha ocurrido una solución bastante ingenua: 1. Busque celdas con celdas con un valor ''0''. 2. Ejecute un DFS (Flood-Fill) cuando encuentre una celda de este tipo (negra) y verifique si podemos tocar el límite de la región rectangular principal 3. Si podemos tocar el límite durante el DFS, entonces no es un agujero y si no podemos alcanzar el límite, se considerará como un agujero
Ahora, esta solución funciona pero me preguntaba si existe alguna otra solución eficiente / rápida para este problema.
Por favor, hágame saber sus pensamientos. Gracias.
El algoritmo de fuerza bruta como se describe here es el siguiente.
Ahora asumimos que podemos escribir en celdas un valor diferente de 0 o 1.
Necesita funciones de relleno de inundación que reciban las coordenadas de una celda para comenzar y un valor entero para escribir en todas las celdas conectadas que tienen el valor 0.
Dado que solo debe considerar los orificios (celdas con valor 0 rodeadas por celdas con valor 1), debe usar dos pases.
Un primer paso visita solo las celdas que tocan el borde. Para cada celda que contiene el valor 0, se realiza un relleno de inundación con el valor -1. Esto le indica que esta celda tiene un valor diferente de 1 y tiene una conexión con el borde. Después de esta exploración, todas las celdas con un valor 0 pertenecen a uno o más orificios.
Para distinguir entre diferentes agujeros, necesita el segundo escaneo. Luego escanea las celdas restantes en el rectángulo (1,1) x (n-2, n-2) que aún no escanea. Cada vez que su escaneo golpeó una celda con valor 0, descubrió un nuevo agujero. Luego llenas este agujero con el entero de tu elección para distinguirlo de los otros. Después de eso, continúe con el escaneo hasta que se hayan visitado todas las celdas.
Cuando haya terminado, puede reemplazar los valores -1 por 0 porque no debería haber ningún 0 a la izquierda.
Este algoritmo funciona, pero no es tan eficiente como el otro algoritmo que propongo. Su ventaja es que es simple y no necesita un almacenamiento de datos adicional para contener los segmentos, la identificación de orificios y la eventual referencia del encadenamiento de segmentos.
Puede representar la cuadrícula como un gráfico con celdas individuales como vértices y bordes que aparecen entre vértices adyacentes. Luego puede usar la Búsqueda en primer lugar o la Búsqueda en primer lugar para comenzar en cada una de las celdas, en los lados. Como solo encontrará los componentes conectados a los lados, las celdas negras que no se han visitado son los orificios. Puede usar el algoritmo de búsqueda nuevamente para dividir los orificios en componentes distintos.
EDITAR: La complejidad del peor de los casos debe ser lineal al número de celdas; de lo contrario, déle algo de entrada al algoritmo, verifique qué celdas (ya que es sublineal, habrá grandes puntos no visitados) que el algoritmo no ha examinado y agujero allí. Ahora tienes una entrada para la cual el algoritmo no encuentra uno de los agujeros.
Su algoritmo es globalmente Ok. Es solo una cuestión de optimizarlo combinando la exploración del relleno de inundación con el escaneo de la celda. Esto solo minimizará las pruebas.
La idea general es realizar la exploración de relleno de inundación línea por línea mientras se escanea la tabla. Así que tendrás múltiples rellenos de inundación paralela que debes seguir.
La tabla se procesa fila por fila de arriba a abajo y cada fila se procesa de derecha a izquierda. El orden es arbitrario, podría ser inverso si lo prefiere.
Permita que los segmentos identifiquen una secuencia de celdas consecutivas con valor 0 en una fila. Solo necesita el índice de la primera y la última celda con valor 0 para definir un segmento. Como puede imaginar, un segmento también es un relleno de inundación en progreso. Entonces, agregaremos un número de identificación a los segmentos para distinguir entre los diferentes rellenos de inundación.
Lo bueno de este algoritmo es que solo necesita realizar un seguimiento de los segmentos y su número de identificación en las filas i e i-1. De modo que cuando procesa la fila i, tiene la lista de segmentos que se encuentran en la fila i-1 y su número de identificación asociado.
A continuación, debe procesar la conexión del segmento en la fila i y la fila i-1. Explicaré a continuación cómo se puede hacer esto eficiente.
Por ahora hay que considerar tres casos:
encontró un segmento en la fila i no conectado a un segmento en la fila i-1. Asígnele una nueva identificación de agujero (entero incrementado). Si está conectado al borde de la tabla, haga que este número sea negativo.
encontró un segmento en la fila i-1 no conectado a un segmento en la fila i-1. Has encontrado el segmento más bajo de un agujero. Si tiene un número de identificación negativo, está conectado al borde y puede ignorarlo. De lo contrario, enhorabuena, has encontrado un agujero.
encontró un segmento en la fila i conectado a uno o más segmentos en la fila i-1. Establezca el número de identificación de todos estos segmentos conectados al número de identificación más pequeño. Vea el siguiente posible caso de uso.
row i-1: 2 333 444 111 row i : **** *** ***
Todos los segmentos de la fila i deberían obtener el valor 1 que identifica el mismo relleno de inundación.
Los segmentos coincidentes en las filas i y la fila i-1 se pueden hacer de manera eficiente manteniéndolos en orden de izquierda a derecha y comparando los índices de los segmentos.
Procese los segmentos por el índice de inicio más bajo primero. Luego verifique si está conectado al segmento con el índice de inicio más bajo de la otra fila. Si no, procese el caso 1 o 2. De lo contrario, continúe identificando los segmentos conectados, manteniendo un registro del número de identificación más pequeño. Cuando no se encuentren más segmentos conectados, configure el número de identificación de todos los segmentos conectados que se encuentran en la fila i al valor de identificación más pequeño.
La comparación del índice para la prueba de conectividad puede optimizarse almacenando (primero-1, último) como definición de segmento, ya que los segmentos pueden estar conectados por sus esquinas. A continuación, puede comparar directamente los valores desnudos de los índices y detectar segmentos superpuestos.
La regla para elegir el número de identificación más pequeño garantiza que obtenga automáticamente el número negativo para los segmentos conectados y al menos uno conectado al borde. Se propaga a otros segmentos y se llena de inundaciones.
Este es un buen ejercicio para programar. No especificaste el resultado exacto que necesitas. Así que esto también se deja como ejercicio.
Con el relleno, que ya tiene : corra a lo largo de la FRONTERA de su matriz y llénelo, es decir, cambie todos los ceros (negro) a 2 (negro relleno) y de uno a 3 (blanco relleno); ignorar 2 y 3 que provienen de una inundación anterior.
Por ejemplo, con su matriz, comienza desde la parte superior izquierda y llena de negro una zona con área 11. Luego se mueve a la derecha y encuentra una celda negra que acaba de llenar. Mueve a la derecha nuevamente y encuentra un área blanca, muy grande (en realidad, todo el blanco en tu matriz). Llenarlo por inundación. Luego te mueves a la derecha otra vez, otra área negra fresca que se extiende a lo largo de todos los bordes superiores y derechos. Moviéndote, ahora encuentras dos glóbulos blancos que rellenaste antes y los saltas. Y finalmente encuentras el área negra a lo largo del borde inferior.
Luego escanee la matriz: todas las áreas que encuentre que aún son de color 0 son agujeros en el negro. También puede tener agujeros en el blanco.
Otro método, una especie de "relleno de inundación detenido"
Corre alrededor del borde de la primera matriz. Donde encuentre "0", establezca en "2". Donde encuentras "1", pones a "3".
Ahora corre alrededor del nuevo borde interior (esas celdas que tocan el borde que acabas de escanear). Las células cero que tocan 2 se convierten en 2, 1 las células que tocan 3 se convierten en 3.
Deberá escanear dos veces, una vez en el sentido de las agujas del reloj, una vez en el sentido contrario a las agujas del reloj, verificando las celdas "hacia afuera" y "antes" de la celda actual. Eso es porque puedes encontrar algo como esto:
22222222222333333
2AB11111111C
31
La celda A es en realidad 1. Examinas a sus vecinos y encuentras 1 (pero es inútil verificar que, como todavía no lo has procesado, no puedes saber si es un 1 o si debería ser un 3, lo cual es el caso , por cierto), 2 y 2. A 2 no puede cambiar un 1, por lo que la celda A permanece 1. Lo mismo ocurre con la celda B, que es nuevamente un 1, y así sucesivamente. Cuando llegas a la celda C, descubres que es un 1 y tiene un 3 vecino, por lo que cambia a 3 ... pero todas las celdas de A a C ahora deberían alternar .
La forma más simple, aunque no más eficiente, de lidiar con esto es escanear las celdas en el sentido de las agujas del reloj, lo que le da una respuesta incorrecta (C y D son 1, por cierto)
22222222222333333
211111111DC333333
33
y luego escanearlos de nuevo en sentido antihorario. Ahora, cuando llega a la celda C, tiene un 3 vecino y cambia a 3. A continuación, inspecciona la celda D, cuyo vecino anterior es C, que ahora es 3, por lo que D cambia a 3 nuevamente. Al final obtienes la respuesta correcta.
22222222222333333
23333333333333333
33
y para cada celda examinó a dos vecinos que iban en el sentido de las agujas del reloj, uno hacia la izquierda. Además, uno de los vecinos es en realidad la celda que verificaste justo antes , para que puedas mantenerla en una variable lista y guardar un acceso de matriz.
Si descubre que ha escaneado un borde completo sin siquiera activar una sola celda, puede detener el procedimiento. Hacer esto te costará 2 operaciones (W * H), por lo que solo vale la pena si hay muchos agujeros.
En la mayoría de los pasos de W * H * 2, debe estar listo.
También es posible que desee comprobar el algoritmo de percolación y tratar de adaptar ese.