fundo
Moldes de lodo são impressionantes. Se você os colocar em uma superfície com fontes de alimento, eles espalharão seus tentáculos para encontrar o alimento, após o que formarão uma rede de conexões entre as fontes. Neste desafio, você deve simular um mofo à procura de comida. Além disso, esse molde em particular irá parar quando for encontrado o suficiente.
Entrada
Suas entradas devem ser uma lista Lde coordenadas inteiras 2D no formato nativo do seu idioma e um número inteiro não negativo N. A lista Lé garantida como livre de duplicatas, mas pode não ser classificada. A entrada Nestá entre 0 e o comprimento de L, inclusive.
A lista Lrepresenta um conjunto de coordenadas para fontes de alimentos. Por exemplo, a lista
[(0,0),(2,-1),(3,1),(0,4),(5,5)]
poderia ser interpretado visualmente como
o
o
o
o
o
Resultado
Sua saída é outra lista livre de duplicatas Kde coordenadas inteiras 2D no mesmo formato da entrada. Representa a rede formada pelo molde de lodo e deve atender às seguintes condições:
- A interseção de
LeKtem tamanho exatamenteN. - O conjunto
Ké conectado como um subconjunto da grade inteira (via adjacências ortogonais ou diagonais). - Se qualquer coordenada de
Kfor removida, ela não atenderá mais às duas primeiras condições.
Observe que se N = 0a saída deve ser uma lista vazia.
Um exemplo de saída aceitável para a lista acima Le N = 4seria
[(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 pode ser visualizado como
xxO
Oxx
x x
x x
x O
O
o
onde cada Oum representa uma coordenada em ambos Le K, e cada xum representa uma coordenada em, Kmas não em L. Outras saídas também são aceitáveis e os "tentáculos" não precisam ser os mais curtos possíveis. Por exemplo, esta também é uma solução aceitável:
xxOxx
Oxx x
x x
x x
x o x
O x
Ox
Regras
Tanto a entrada como a saída devem ser listas, não conjuntos ou outros tipos de dados. As próprias coordenadas podem ser listas ou tuplas. Você pode alterar a ordem das duas entradas, se necessário.
Você pode escrever um programa completo ou uma função. A menor contagem de bytes vence e as brechas padrão não são permitidas.
Casos de teste
Seu programa deve trabalhar nessas listas para todos os valores aplicáveis 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
fonte