Введение
Есть небольшая деревня, в которой только несколько домов и пустые поля. Местные бюрократы хотят разделить деревню на участки, чтобы каждый участок содержал ровно один дом, а границы участков образуют красивую прямолинейную сетку. Ваша задача - определить, возможно ли это.
Задание
Ваш вход представляет собой прямоугольный двумерный массив битов; 1 представляет дом, а 0 - пустое поле. Его размер будет по крайней мере 1 × 1 , и он будет содержать по крайней мере один 1. Вы можете взять ввод в любом разумном формате (вложенный список целых чисел, список строк, многострочная строка и т. Д.).
Ваша программа должна определить, можно ли разбить массив на ячейки сетки, используя прямые горизонтальные и вертикальные линии, чтобы каждая ячейка сетки содержала ровно одну единицу. Ячейки сетки могут иметь разные размеры и формы, хотя они всегда будут прямоугольными. Линии должны проходить от одного края массива до противоположного края.
Например, следующее является допустимым разделением массива:
00|0010|01|1
01|0000|00|0
--+----+--+-
00|0000|00|1
01|0010|01|0
--+----+--+-
01|1000|10|1
тогда как следующее деление недопустимо, так как существуют ячейки сетки без 1 или более 1:
00|0010|01|1
--+----+--+-
01|0000|00|0
00|0000|00|1
01|0010|01|0
--+----+--+-
00|1000|10|1
Если допустимое деление существует, вы должны вывести истинное значение, а в противном случае ложное значение.
Правила и оценки
Вы можете написать полную программу или функцию. Побеждает самое низкое число байтов.
Контрольные примеры
[[1]] -> True
[[0,1],[1,0]] -> True
[[1,1],[1,0]] -> False
[[1,0,1],[0,1,0]] -> True
[[1,0],[0,1],[0,1]] -> True
[[1,0,0],[0,0,1],[0,1,1]] -> True
[[1,1,1],[1,1,1],[1,1,1]] -> True
[[1,0,1],[0,1,0],[1,0,0]] -> True
[[1,0,0],[1,0,0],[0,1,1]] -> False
[[0,0,0,0,1],[1,0,0,1,0],[0,0,0,1,0]] -> False
[[0,0,1,0,1],[0,0,0,1,0],[0,0,0,0,0]] -> True
[[1,1,0,0,0],[0,0,0,0,0],[1,0,1,0,0]] -> True
[[1,1,0,1,1],[0,1,0,1,1],[1,0,0,0,0]] -> True
[[0,0,0,0,0,0,0],[0,1,1,1,0,1,0],[0,1,0,0,1,0,0],[0,0,0,0,0,0,1],[0,0,1,0,0,0,1],[1,1,0,1,1,0,0]] -> False
[[1,1,0,0,0,0,0],[1,0,1,1,0,1,0],[0,0,0,0,1,0,0],[0,1,0,1,1,0,0],[1,0,0,0,1,1,0],[0,0,0,0,0,1,0]] -> False
[[0,1,0,1,1,1,0],[0,0,0,0,1,0,0],[0,0,0,0,0,0,0],[1,0,0,1,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,1]] -> True
[[0,1,0,0,1,0,1],[1,0,0,0,1,0,1],[0,0,1,0,1,0,1],[1,0,0,0,1,1,0],[0,0,0,1,1,1,0],[0,1,0,0,1,0,1]] -> True
[[0,1,0,0,1,0,0,1,0],[0,0,0,0,1,1,0,1,0],[1,1,0,0,1,0,0,0,0],[0,0,1,0,1,0,1,0,0],[0,0,1,0,1,0,1,0,0],[0,1,0,0,0,1,0,0,1],[0,1,0,0,0,0,1,0,0]] -> False
[[1,0,1,0,0,1,1,0,1],[0,1,1,0,0,1,1,0,1],[1,0,0,0,0,1,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,1,1],[0,1,1,0,1,0,1,0,1],[1,0,1,0,0,1,1,0,1]] -> True
[[1, 0, 1], [0, 1, 0], [1, 0, 0]]
это была единственная матрица 3х3, для которой мой новый подход не удался.Ответы:
Pyth,
3029262423 байтаПопробуйте онлайн.
Я уверен, что это станет короче. Это O (2 mn ) , где m и n - ширина и высота массива, но завершает последние два теста за 45 секунд на моем ноутбуке от батареи (i5-5200U с ограниченной производительностью).
Выводит количество решений.
объяснение
С пятимерными массивами работать очень интересно. </ sarcasm> Вы не должны понимать, как это работает, даже с объяснениями.
источник
Желе , 22 байта
Попробуйте онлайн!
источник
Haskell , 116 байт
Попробуйте онлайн!
источник
mergerows
вm
.[[1,0],[0,1],[1,0]]
. Проблема в том, что жадный крах может помешать более позднему лучшему краху.[[1,1],[1,0]]
крах ложно мешает[[1],[1],[1]]
решению проблемы. Позвольте мне спать по этому или я должен удалить?Желе , 20 байт
Это все еще грубое решение, но оно намного быстрее, чем мой другой ответ - который не справляется с последними двумя тестовыми примерами на TIO - и обрабатывает все тестовые случаи за ~ 4 секунды.
Попробуйте онлайн!
Как это работает
источник