Contexte
Les moules visqueux sont impressionnants. Si vous les placez sur une surface avec des sources de nourriture, ils étaleront leurs vrilles pour trouver la nourriture, après quoi ils formeront un réseau de connexions entre les sources. Dans ce défi, vous simulerez un moule visqueux à la recherche de nourriture. De plus, ce moule particulier s'arrêtera une fois qu'il sera suffisamment trouvé.
Contribution
Vos entrées doivent être une liste Lde coordonnées entières 2D dans le format natif de votre langue, et un entier non négatif N. La liste Lest garantie sans doublon, mais elle ne peut pas être triée. L'entrée Nest comprise entre 0 et la longueur de L, inclus.
La liste Lreprésente un ensemble de coordonnées pour les sources de nourriture. Par exemple, la liste
[(0,0),(2,-1),(3,1),(0,4),(5,5)]
pourrait être interprété visuellement comme
o
o
o
o
o
Production
Votre sortie est une autre liste sans doublon Kde coordonnées entières 2D sur le même format que l'entrée. Il représente le réseau formé par la moisissure visqueuse et doit satisfaire aux conditions suivantes:
- L'intersection de
LetKa exactement la tailleN. - L'ensemble
Kest connecté en tant que sous-ensemble de la grille entière (via des contiguïtés orthogonales ou diagonales). - Si une coordonnée de
Kest supprimée, elle ne remplit plus les deux premières conditions.
Notez que si N = 0, la sortie doit être une liste vide.
Un exemple de sortie acceptable pour la liste ci-dessus Let N = 4serait
[(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)]
qui peut être visualisé comme
xxO
Oxx
x x
x x
x O
O
o
où chacun Oreprésente une coordonnée dans les deux Let K, et chacun xreprésente une coordonnée dans Kmais pas dans L. D'autres sorties sont également acceptables, et les "vrilles" ne doivent pas être les plus courtes possible. Par exemple, c'est également une solution acceptable:
xxOxx
Oxx x
x x
x x
x o x
O x
Ox
Règles
L'entrée et la sortie doivent être des listes et non des ensembles ou d'autres types de données. Les coordonnées elles-mêmes peuvent être des listes ou des tuples. Vous pouvez modifier l'ordre des deux entrées si nécessaire.
Vous pouvez écrire soit un programme complet soit une fonction. Le nombre d'octets le plus bas gagne et les failles standard sont interdites.
Cas de test
Votre programme doit fonctionner sur ces listes pour toutes les valeurs applicables 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)]
Visualisé:
===
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
la source