题目背景

原题 P11752 [COCI 2024/2025 #5] 挂画 / Zid

题目描述

有一面 $n$ 行 $m$ 列的矩形墙，被划分为 $n\times m$ 个区域。墙上有些区域有钉子，用 $\texttt{\#}$ 表示；其他的区域没有钉子，用 $\texttt{.}$。

现在要在墙上挂画。我们说一种挂画方式是合法的，当且仅当：

• 画占据墙上的一个矩形区域；
• 画占据的区域中至多一个区域存在钉子。

求出有多少种合法的挂画方式。

输入格式

第一行，两个正整数 $n,m$。

接下来 $n$ 行，第 $i$ 行一个字符串 $c$，$c_{i,j}$ 表示墙上第 $i$ 行第 $j$ 列的区域的状态。

输出格式

输出一行一个正整数表示答案。

输入输出样例 #1

输入 #1

3 3
...
...
..#

输出 #1

36

输入输出样例 #2

输入 #2

4 4
....
.#..
#...
#.#.

输出 #2

76

输入输出样例 #3

输入 #3

5 5
.....
#..#.
..#.#
.....
..#..

输出 #3

154

说明/提示

样例解释

• 样例 $1$ 解释：随便怎么放都是合法的。

数据范围

对于 $100\%$ 的数据，保证 $1\le n\le 500$。