Dadas dos formas contiguas de la misma área, determine la forma óptima de dividir la primera forma en un número mínimo de segmentos contiguos de modo que puedan reorganizarse para formar la segunda forma. En otras palabras, encuentre el número mínimo de segmentos requeridos que pueden formar ambas formas.
"Contiguo" significa que se puede llegar a cada cuadrado de la forma desde cualquier otro cuadrado caminando a través de los bordes. Se permite que las formas y los segmentos tengan agujeros.
"Reorganizar" significa que mueve los segmentos; puedes traducirlos, rotarlos y reflejarlos.
Las formas están contenidas en una cuadrícula; en otras palabras, cada forma consiste en una colección de cuadrados unitarios unidos por sus esquinas / bordes.
Especificaciones de entrada
La entrada se proporcionará en un formato razonable: lista de puntos, conjunto de cadenas que representan cada cuadrícula, etc. También puede tomar los tamaños de la cuadrícula si se solicita. Las cuadrículas tendrán las mismas dimensiones y se garantiza que las dos formas tendrán la misma área, y el área será positiva.
Especificaciones de salida
La salida debería ser solo un entero positivo. Tenga en cuenta que siempre habrá una respuesta positiva porque en el peor de los casos, simplemente divide las formas en N
cuadrados unitarios.
Ejemplos
Los ejemplos se presentan como una cuadrícula que .
representa un espacio en blanco y que #
representa parte de la forma.
Caso 1
Entrada
.....
.###.
.#.#.
.###.
.....
###..
..#..
..#..
..###
.....
Salida
2
Explicación
Puedes dividirlo en dos bloques en forma de L de 4:
#
###
Caso 2
Entrada
#...
##..
.#..
.##.
.##.
####
....
....
Salida
2
Explicación
Puedes dividir las formas así:
A...
AA..
.A.
.BB.
.AA.
BBAA
....
....
También puedes hacer:
A...
AA..
.B..
.BB.
.AB.
AABB
....
....
Caso 3
Entrada
#....#
######
.####.
.####.
Salida
2
Explicación
A....B
AAABBB
.ABBB.
.AAAB.
(Este caso de prueba demuestra la necesidad de rotar / reflejar formas para una salida óptima)
Caso 4
Entrada
.###.
..#..
.##..
.##..
Salida
2
Explicación
No importa cómo seleccione los bloques, seleccionar un 2x1 de la primera forma necesariamente evita que los otros dos se agrupen; por lo tanto, puede usar un 2x1 y dos 1x1s. Sin embargo, (gracias @Jonah), puede dividirlo en una forma de L de 3 bloques y un solo cuadrado de esta manera:
.AAB.
..A..
.AA..
.BA..
Respuestas:
Python 3.6 ,
799791 bytes7 bytes guardados por Jonathan Frech y motavica
Pruébalo en línea!
Uso
A(s, t)
toma dos formas donde cada forma está dada por una lista dex, y
posiciones de la cuadrícula.A continuación se muestra una función auxiliar para convertir la representación gráfica en una lista de posiciones:
Ejemplo:
Explicación
El algoritmo utilizado aquí es un poco mejor que la fuerza bruta al almacenar en caché las subformas. Para una forma dada, almacena en caché todas las formas de dividir esa forma en dos formas contiguas, luego normalizo estas formas (desplazo las coordenadas para que comience en el origen, luego encuentro una rotación / reflexión de la misma que se usa en el caché) y guárdelos en el caché para buscarlos rápidamente más tarde. Todas las subformas tienen sus subformas almacenadas en caché también hasta que llegue a la forma de bloque único.
Estas subformas se generan convirtiéndolas en una lista de adyacencia de gráficos y usando un BFS para generar todos los sub-gráficos. Luego podemos filtrar estas subgrafías a aquellas donde los vértices que no se incluyeron son un componente conectado. La determinación de si el gráfico está conectado se realiza con otro BFS.
Una vez que se completa el caché, la solución se encuentra comparando las dos formas para encontrar las subformas que tiene en común. Una vez que tiene esta lista de subformas, toma el par de subformas sobrantes después de eliminar la forma común y aplica recursivamente el mismo algoritmo nuevamente para encontrar el número mínimo de bloques necesarios para reconstruir la forma. Esto devuelve la subforma con el mínimo de todos esos valores y tenemos nuestra solución.
Puse una versión anotada a continuación para explicar un poco lo que está haciendo cada línea.
fuente
if s==t else
posiblemente podría revertirse, permitiendo el reemplazo de!=
a^
.if i<len(s)-1else
~>if-~i<len(s)else
.def A(s,t):U(s);U(t);return V(P(s),P(t))
posiblemente podría serlambda s,t:U(s)or U(t)or V(P(s),P(t))
, ahorrando tres bytes.s.union(*[g[n]for n in s])
~>s.union(*map(g.get,s))