Вы участвуете в испытаниях нового оружия. Для испытаний создан полигон, представляющий собой прямоугольное поле размера n × m, разделенное на единичные квадраты 1 × 1. На полигоне расположено k объектов, каждый из которых является прямоугольником со сторонами, параллельными сторонам полигона, занимающим полностью несколько единичных квадратов. Объекты не пересекаются и не касаются друг друга.
Принцип действия оружия сверхсекретен. Вам известно лишь то, что с помощью него можно нанести удар по любой прямоугольной области ненулевой площади со сторонами, параллельными сторонам полигона. Область должна накрывать полностью некоторые из единичных квадратов, на которые разбит полигон, и никак не затрагивать остальные квадраты. Разумеется, область не должна выходить за границы полигона. При этом вам поставлена задача: поразить не менее одного и не более трех прямоугольных объектов. Каждый объект должен лежать либо целиком внутри области (тогда он считается пораженным), либо целиком вне области.
Посчитайте количество способов нанести удар.
В первой строке содержатся три целых числа n, m и k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 90) — размеры полигона и количество объектов на нем, соответственно. Следующие n строк содержат по m символов каждая и описывают полигон. Символ «*» означает, что соответствующий квадрат на полигоне занят объектом, символ «.» обозначает пустое пространство. Гарантируется, что символы «*» образуют ровно k связных прямоугольных областей, отвечающих условию задачи.
Выведите единственное число — количество способов нанести удар.
3 3 3
*.*
...
*..
21
4 5 4
.*.**
...**
**...
...**
38
2 2 1
.*
..
4
Название |
---|