Задание 9.
Мозаика
Компания «Headache», занимающаяся выпуском логических игрушек для детей, представила свою новую мозаику. В нее входит прямоугольная пластина, состоящая из N*M квадратов. Некоторые квадраты пластины изначально заняты, и в них ничего нельзя поставить. В комплекте поставляются также детали для складывания мозаики. Различных типов деталей всего 9, пронумерованы они от 1 до 9 в том порядке, в котором изображены на рисунке:
.
Конструкция каждой детали не позволяет поставить ее на пластину как бы то ни было повернутой. Все типы деталей являются различными, и нельзя с помощью поворота получить деталь другого типа. Деталь можно поставить только на свободные квадраты. Конструкция деталей была тщательно продумана, поэтому с помощью деталей 3 и 4 можно, например, сложить квадрат 2*2. В наборе деталей каждого типа достаточно для того, чтобы не заботиться об их количестве.
Каждый тип детали имеет свой уникальный цвет. Мозаика называется сложенной, если все квадраты пластины заняты. Два мозаичных узора различны, если есть квадраты, занятые деталями различных типов (цветов). Создателям очень хочется знать, сколько различных узоров сложенной мозаики может получиться. Это необходимо им для рекламной кампании. Ваша задача – помочь им разобраться в этом непростом вопросе.
Формат ввода
В первой строке находятся N – размер пластины по вертикали, и M – размер пластины по горизонтали. Затем в следующих N строках находятся ровно по M чисел, равных нулю или единице. Единица обозначает занятый квадрат, ноль – свободный.
Формат вывода
В первой строке должно находиться единственное число, равное количеству различных узоров сложенной мозаики.
.
Найдите число различных узоров для следующей структуры (доступно для копирования в буфер обмена):
8 6
0 1 0 0 0 1
1 0 1 0 0 1
1 0 1 0 1 1
0 1 0 0 1 1
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 1 1 1 1 1
Ответ: 45.
Задание 10.
Японский гексаворд
Все (или многие) знают, что такое японский кроссворд. Он располагается на прямоугольном поле. В отличие от него гексаворд располагается на шестиугольном поле в виде пчелиных сот. А количество закрашенных клеток задается не по двум координатам (вертикали и горизонтали) а по трем, как показано на рисунке 1.
Направления нумеруются против часовой стрелки, начиная с верхнего западного. Для рисунка 1) нумерация количества закрашенных в каждом направлении клеток следующая:
2 1 1
2 1 1
0 2 2.
Требуется по имеющимся числовым значениям (обозначающим общее число закрашенных сот в данном направлении) сосчитать количество различных вариантов закраски гексаворда.
Формат входных данных (файл Gex.in)
В первой строке входного файла содержится натуральное нечетное число N (1<=N<=7). В следующих 3 строках содержатся по N разделенных пробелами натуральных чисел в диапазоне от 0 до N.
Количество чисел равно 3*N. Для рисунка 1) N=3, для рисунка 2) N=5 и для рисунка 3) N=7.
Формат выходных данных (файл Gex.out)
В выходной файл необходимо вывести одно целое число – количество различных вариантов закраски гексаворда.
Составьте программу и просчитайте для трех тестовых файлов Gex.in (доступно для копирования в буфер обмена):
Тест1
7
1 2 3 4 3 2 1
1 2 3 4 3 2 1
1 2 3 4 3 2 1
Тест 2
7
1 2 3 4 3 2 1
1 2 3 4 3 2 1
1 2 3 4 3 2 1
Тест 3
5
1 3 2 3 1
1 3 2 3 1
1 3 2 3 1.
В ответе запишите результаты тестов через запятую, без пробелов.
Пример входных, выходных данных и вывода ответа.
Запись ответа: 2,1,28
Ответ: 388,4,8.