Ограничение по времени: 3.000 секунд
Ограничение по памяти: 200.000 мегабайт
Недавно Костя переехал в новый кабинет и теперь хочет поставить там свой стол. К решению этого вопроса он подошел с математической точки зрения.
Кабинет можно упрощенно представить как клетчатый прямоугольник из n строк и m столбцов. Костя знает, что его стол займет ровно две клетки, имеющих общую горизонтальную или вертикальную сторону. Еще он знает, что некоторые клетки уже заняты мебелью других коллег, и они не могут быть заняты еще и его столом. Теперь он хочет знать количество способов разместить свой стол в кабинете. Помогите ему с решением этой задачи.
Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 1 000) - размеры кабинета. Каждая из следующих n строк содержит по m символов - описание кабинета. Символ # означает, что соответствующая клетка уже чем-то занята, а символ . - что она свободна и может стать одной из двух, занятых столом.
Выведите одно целое число - количество способов разместить стол в кабинете.
| input | output |
|---|---|
1 1 . |
0 |
2 3 ... ... |
7 |
3 4 ..#. #..# ..#. |
5 |
5 8 ........ .##..##. ........ #......# .######. |
34 |