@Отман

Мультипликативный кроссворд
Тур II, задача 4

Наступил далекий 3102 год. Уже все классические кроссворды давно разгаданы. Не так давно суперкомпьютер «Фёдор» предложил обществу новый вид кроссвордов. Новый кроссворд представляет собой прямоугольную таблицу с N строками и M столбцами. Строки нумеруются сверху вниз, начиная с единицы, а столбцы слева направо, начиная с единицы, что, конечно, не сильно отличает новый вид от прежних (классических, скандинавских, японских, числовых и др.). Основное отличие этого вида кроссвордов в том, что загадывается не слово, а произведение чисел в определенной горизонтальной или вертикальной области кроссворда. Называть такие кроссворды «Фёдор» предложил мультипликативными.

Рисунок №1. Мультипликативный кроссворд. N=4, M=4, загадано 4 произведения 36 (2 вертикальных и 2 горизонтальных).

Мультипликативные кроссворды завоевывали все большую любовь эрудитов, когда другой суперкомпьютер «Степан» предложил уменьшить неопределенность в решение кроссвордов. И тогда добавилось новое требование к решению кроссворда «Клеток, в которых стоит число 1, должно быть как можно меньше!».

Рисунок №2. Улучшенное решение мультипликативного кроссворда.

Для проверки корректности составления мультипликативного кроссворда Вас просят написать программу, которая находит количество вырезанных клеток (содержащих символ '#') в нём.
Входные данные

Первая строка входного файла содержит три целых числа N, М и K, разделенные одиночными пробелами.
Каждая из следующих N строк входного файла содержит строковую величину, состоящую ровно из M символов, где j-й символ i-й строки описывает одну клетку кроссворда, находящуюся в строке i и столбце j. Если символ равен “.” (ASCII 46), то в соответствующую клетку нужно поставить число, если символ равен “#” (ASCII 35) – клетка не принадлежит ни одному загаданному произведению.
Каждая из последующих K строк содержит по одному описанию загаданного произведения. Каждое описание состоит из пяти целых чисел D, R, C, L и V, разделенных одиночными пробелами. D равно 1, если область, где загадано произведение, расположена по горизонтали, и равно 2, если по вертикали; R задает номер строки, а C – номер столбца левого верхнего угла области; L – длина области в клетках; V – загаданное произведение. Области могут касаться, но иметь общие клетки могут, только области разной направленности, т.е. горизонтальная и вертикальная.
Известно, что мультипликативный кроссворд из входного файла имеет хотя бы одно решение.
Выходные данные

Ответ - одно число - количество символов '#" в заданном кроссворде.

Пример ввода-вывода

input.txt
4 8 8
........
.##..##.
.##..##.
........
1 1 1 8 64
2 1 1 4 4
2 1 4 4 4
2 1 5 4 16
2 1 8 4 16
1 2 4 2 2
1 4 1 4 4
1 4 5 4 16
output.txt
8



Заранее спасибо!!!

0

@Puporev

Заранее пожалуйста! Привет рисункам №1 и №2.

0