Фон
Формы слизи потрясающие. Если вы разместите их на поверхности с источниками пищи, они разложат свои усики, чтобы найти пищу, после чего они образуют сеть связей между источниками. В этом задании вы будете имитировать слизистую плесень в поисках пищи. Более того, эта конкретная плесень остановится, как только она будет найдена.
вход
Ваши входные данные должны быть списком Lдвумерных целочисленных координат в родном формате вашего языка и неотрицательным целым числом N. Список Lгарантированно не содержит дубликатов, но он не может быть отсортирован. Ввод Nот 0 до длины Lвключительно.
Список Lпредставляет собой набор координат для источников пищи. Например, список
[(0,0),(2,-1),(3,1),(0,4),(5,5)]
можно интерпретировать визуально как
o
o
o
o
o
Вывод
Ваш вывод представляет собой другой список Kдвумерных целочисленных координат без дубликатов в том же формате, что и ввод. Он представляет собой сеть, образованную слизистой плесенью, и должен удовлетворять следующим условиям:
- Пересечение
LиKимеет размер точноN. - Набор
Kсвязан как подмножество целочисленной сетки (через ортогональные или диагональные смежности). - Если какая-либо координата
Kудалена, она больше не удовлетворяет первым двум условиям.
Обратите внимание, что если N = 0, выход должен быть пустой список.
Примером приемлемого вывода для приведенного выше списка Lи N = 4будет
[(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)]
который может быть визуализирован как
xxO
Oxx
x x
x x
x O
O
o
где каждый Oпредставляет координату в обоих Lи K, и каждый xпредставляет координату в, Kно не в L. Другие результаты также приемлемы, и «усики» не должны быть максимально короткими. Например, это также приемлемое решение:
xxOxx
Oxx x
x x
x x
x o x
O x
Ox
правила
И вход, и выход должны быть списками, а не наборами или другими типами данных. Сами координаты могут быть списками или кортежами. Вы можете изменить порядок двух входов, если это необходимо.
Вы можете написать либо полную программу, либо функцию. Побеждает меньшее количество байтов, и стандартные лазейки запрещены.
Тестовые случаи
Ваша программа должна работать с этими списками для всех применимых значений 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)]
Визуализация:
===
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
источник