Antecedentes
Los moldes de limo son increíbles. Si los coloca en una superficie con fuentes de alimento, extenderán sus zarcillos para encontrar el alimento, luego de lo cual formarán una red de conexiones entre las fuentes. En este desafío, simularás un molde de limo buscando comida. Además, este molde particular se detendrá una vez que se encuentre lo suficiente.
Entrada
Sus entradas serán una lista Lde coordenadas enteras 2D en el formato nativo de su idioma, y un número entero no negativo N. Se Lgarantiza que la lista no tendrá duplicados, pero es posible que no se ordene. La entrada Nestá entre 0 y la longitud de L, inclusive.
La lista Lrepresenta un conjunto de coordenadas para las fuentes de alimentos. Por ejemplo, la lista
[(0,0),(2,-1),(3,1),(0,4),(5,5)]
podría interpretarse visualmente como
o
o
o
o
o
Salida
Su salida es otra lista libre de duplicados Kde coordenadas enteras 2D en el mismo formato que la entrada. Representa la red formada por el molde de limo y debe cumplir las siguientes condiciones:
- La intersección de
LyKtiene tamaño exactamenteN. - El conjunto
Kestá conectado como un subconjunto de la cuadrícula entera (a través de adyacencias ortogonales o diagonales). - Si
Kse elimina cualquier coordenada de , ya no cumple las dos primeras condiciones.
Tenga en cuenta que si N = 0, la salida debe ser una lista vacía.
Un ejemplo de una salida aceptable para la lista anterior Ly N = 4sería
[(0,0),(0,1),(0,2),(0,3),(0,4),(1,4),(2,4),(3,3),(3,2),(3,1),(3,5),(4,5),(5,5)]
que se puede visualizar como
xxO
Oxx
x x
x x
x O
O
o
donde cada uno Orepresenta una coordenada en ambos Ly K, y cada uno xrepresenta una coordenada en Kpero no en L. Otros resultados también son aceptables, y los "zarcillos" no tienen que ser lo más cortos posible. Por ejemplo, esta también es una solución aceptable:
xxOxx
Oxx x
x x
x x
x o x
O x
Ox
Reglas
Tanto la entrada como la salida serán listas, no conjuntos u otros tipos de datos. Las coordenadas mismas pueden ser listas o tuplas. Puede cambiar el orden de las dos entradas si es necesario.
Puede escribir un programa completo o una función. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.
Casos de prueba
Su programa debería funcionar en estas listas para todos los valores aplicables de N.
[]
[(2,3)]
[(0,0),(1,0),(0,1),(1,1)]
[(0,0),(2,-1),(3,1),(0,4),(5,5)]
[(0,0),(1,0),(2,0),(3,0),(0,3),(1,3),(2,3),(3,3)]
[(0,0),(1,0),(2,0),(3,0),(0,3),(1,3),(2,3),(3,3),(0,1),(0,2),(3,1),(3,2),(8,1),(8,2),(-5,1),(-5,2)]
[(0,0),(20,0),(15,15),(-10,4),(-10,3),(0,-5),(7,6),(7,7),(8,8),(9,8),(10,-2),(-1,12),(-3,10)]
[(0,0),(1,0),(2,0),(3,0),(5,0),(6,0),(7,0),(0,9),(1,9),(2,9),(3,8),(4,9),(5,10),(6,10),(7,9),(3,3),(4,4),(5,5)]
Visualizado:
===
o
===
oo
oo
===
o
o
o
o
o
===
oooo
oooo
===
oooo
o o o o
o o o o
oooo
===
o
o
o
oo
o
o
o
o
o o
o
o
===
oo
ooo o o
o
o
o
o
oooo ooo
fuente