Эта задача основана на игре Layerz.
Учитывая, в stdin или в качестве аргумента функции, 2D прямоугольный массив ячеек, где каждая ячейка содержит либо пробел (вы можете использовать 0 вместо пробелов без штрафа), 1, 2, 3 или 4 ; найдите способ разделить его на допустимые области (как определено ниже) так, чтобы каждая непустая ячейка содержалась ровно в одной области. Затем выведите найденное решение в любом приемлемом формате. Если решения не существует, либо прекратите работу, не создавая выходных данных, либо выведите одно значение фальси, затем остановите.
Любое из следующего составляет допустимый регион:
- Отдельная ячейка, содержащая 1
- Ячейка, содержащая 2 и ровно один из ее непустых ортогональных соседей
- Ячейка, содержащая 3 и ровно два из ее непустых ортогональных соседей
- Ячейка, содержащая 4 и ровно три из ее непустых ортогональных соседей
Это код-гольф , поэтому самый короткий действительный ответ в байтах выигрывает.
Некоторые тестовые случаи:
1. Довольно тривиально:
И это решение, где каждый регион имеет свой цвет:
2. Более интересный
У этого есть более одного решения, но вот одно из них:
3. Меньший, содержащий пробелы, который не имеет никаких решений (в зависимости от того, используете ли вы одну из двойок, чтобы «захватить» тройку, или тройку, чтобы взять две из двойок, у вас либо останется пара несмежных (и, следовательно, не группируемых) пар или две пары самостоятельно):
Поскольку эта сетка не имеет решений, ваша программа должна останавливаться без вывода каких-либо данных при наличии этой сетки.
4. Этот (с двумя верхними смещенными на одну ячейку влево) имеет решение, хотя:
Решение:
(Внизу справа 2 используется для «захвата» 3)
5. Потому что нам нужен был тестовый пример с несколькими четверками:
Одно из решений:
источник
4
s, если они являются действительными входными данными.Ответы:
Я знаю, что этому вызову больше года, но я нашел это в «без ответа» и выглядел довольно интересным для меня.
Предполагая, что номер «корневой» ячейки является единственным значимым в каждой области (выводим из примеров), вот мое решение для отслеживания:
Python 3 ,
355351349 байтПопробуйте онлайн!
Входной формат представляет собой двумерный список целых чисел, пробелы равны нулю, а выходной формат также представляет собой двумерный список целых чисел, представляющих одну область на число. Номер региона начинается с единицы; ноль зарезервирован для пустых ячеек (как на входе). Если данный вход неразрешим, функция возвращает один ноль (ложное значение).
Например, тестовый пример 5 вводится как
и вывод
Ungolfed, с комментариями:
Попробуйте онлайн!
Примечание. Это особый случай комплектной упаковки, которая, как известно, является NP-полной. Эта конкретная проблема имеет ограниченный размер набора (макс. 4) и существуют алгоритмы аппроксимации, чтобы найти «хорошую» упаковку наборов за полиномиальное время, но они не гарантируют максимально возможную упаковку наборов (что строго необходимо в этой задаче).
источник