Patrón de dos dimensiones rápido que coincide

Question

Considere una cuadrícula bidimensional (la retícula habitual en el plano). Para mis propósitos, un patrón o acuerdo es una asignación de los números 1 y 2 a algún subconjunto conectado de los puntos de la grilla. Por ejemplo, los siguientes espectáculos tres acuerdos separados:

.......1.....1.... 
.222...2.....12... 
.111...2.....2.... 
.222...22...12211. 
.......1....11.1.. 

me dicen que un pequeño patrón coincide con uno grande, si el pequeño se puede girar o reflejada de manera que todos sus números son más pequeños que los números en la mayor uno. Por ejemplo, considere este patrón:

...... 
.1212. 
....2. 
...... 

que no coincide con la disposición más a la izquierda arriba, ya que no se puede girar o reflejada para caber en un cuadrado de 3x3. SÍ HACE coincidir con la disposición del medio porque se puede girar y reflejar para que quepa debajo. Sin embargo, NO coincide con la disposición más a la derecha porque, sin embargo, se gira o se refleja para encajar en la disposición más a la derecha, los números son más grandes en el patrón pequeño que en la disposición grande. (Si alguno de mis ejemplos no está claro o si necesita más información, simplemente solicite información en el área de comentarios. Algunas aclaraciones por adelantado: el patrón no se puede estirar, y no se puede girar, por lo que es diagonal con respecto a la cuadrícula . Eso significa que hay cuatro rotaciones y cuatro reflexiones totales, cada uno de los cuales se pueden traducir)

me pregunto acerca de las siguientes preguntas:.

1. ¿Cómo puedo comprobar rápidamente si un pequeño patrón coincide con una gran arreglo?

2. Supongamos que tengo muchos patrones pequeños. ¿Puedo preprocesarlos de alguna manera para decir rápidamente si al menos un coincide con un arreglo?

supongo que sería genial si una solución resuelve un problema más general (como números arbitrarios - no sólo los 1 y 2 - o que permiten formas desconectadas), pero en realidad sólo se preocupan por el caso anterior . Gracias.

Answer 1

convolución 2D.
(la complejidad es n * Log (n) donde n en número de elementos) y podría ser bueno para matrices más grandes.

Haga que ambas matrices coincidan y no coincidan con el mismo tamaño.

Pruebe cada número por separado. Ejemplo - cheking número k En matriz serchung (más grande) establecen números de> = k en otros valores 0 en 1
En valores de ajuste de matriz patteren < = k en 1 otro conjunto en 0

Cuando el resultado de la convolución es 0 es golpeado y partido

de verificación para cada rotación y reflexión (8 en total)

eso significa que comlexity general es k n log (n) donde k es el número de números (en su caso 2) y n número de elementos de una matriz más grande)