Задача 102782

Темы:    [ Динамическое программирование (прочее) ] [ Длинная арифметика как инструмент ]

Сложность: 3+ Классы: Название задачи: Дырокол .

Условие

Квадратный клетчатый лист бумаги 2^N × 2^N клеток начинают складывать следующим образом. Сначала нижняя половина листа накладывается на верхнюю, затем правая половина листа накладывается на левую. Эту операцию повторяют N-3 раза, в результате чего получается сложенный лист 8 × 8 клеток. Какие-то из клеток этого сложенного листа удаляются при помощи дырокола.

После развертывания исходный лист распадется на некоторое количество связных частей, т.е. таких множеств клеток, что из любой клетки одного множества можно пройти до любой другой, переходя каждый раз на соседнюю по вертикали или горизонтали клетку. Напишите программу, вычисляющую число частей, на которые распадется лист.

Входные данные
Первая строка входного файла содержит целое число N (4 ≤ N ≤ 500). В следующих 8 строках записана матрица 8 × 8 из нулей и единиц, разделенных пробелом. Единицами отмечены клетки, выкалываемые дыроколом из сложенного листа 8 × 8.

Выходные данные
Вывести в выходной файл искомое число частей.

Пример входного файла
4
0 1 0 0 0 0 1 0
1 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 0 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0

Пример выходного файла
11

Решение

Скачать архив тестов и решений

Каждую связную область сложенного листа (если смотреть на него сверху) закодируем двоичным числом b₃b₂b₁b₀ . А именно, положим b₀ равным единице, если эта область примыкает к нижней границе листа, и нулю в противном случае. Числа b₁ , b₂ и b₃ определим аналогичным образом для верхней, правой и левой границ листа соответственно. Тем самым, все области разбиваются на 16 типов в соответствии с их кодами. Теперь проанализируем, что происходит с областями при развертывании листа. 

Рассмотрим, например, разгибание относительно нижней стороны. Легко заметить, что связная область типа b₃b₂b₁1 перейдет в связную область типа b₃b₂b₁b₁ (действительно, будет ли она прилегать к нижнему краю после разгибания зависит от того, прилегала ли она к верхнему до разгибания). Связная область типа b₃b₂b₁0 после разгибания распадется на две. Одна из них будет иметь тот же тип b₃b₂b₁0, а другая – тип b₃b₂0b₁. Аналогично анализируется разгибание листа относительно правой стороны.

Для решения задачи проделываем 2N разгибаний, обратных произведенным при складывании листа сгибаниям. При этом на каждом шаге пересчитываем количество связных областей каждого из типов.

Источники и прецеденты использования

книга
предмет	информатика
Автор	Беров В., Лапунов А., Матюхин В., Пономарев А.
Название	Особенности национальных задач по информатике
Издательство	Триада-С
Год издания	2000
глава
Номер	1
Название	Динамическое программирование
Задача
Номер	5