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

[COCI 2024/2025 #5] 挂画 / Zid

题目背景

译自 COCI 2024/2025 #5 T2。1s,0.5G\texttt{1s,0.5G}。满分为 7070

题目描述

有一面 nnmm 列的矩形墙,被划分为 n×mn\times m 个区域。墙上有些区域有钉子,用 #\texttt{\#} 表示;其他的区域没有钉子,用 .\texttt{.}

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

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

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

输入格式

第一行,两个正整数 n,mn,m

接下来 nn 行,第 ii 行一个字符串 ccci,jc_{i,j} 表示墙上第 ii 行第 jj 列的区域的状态。

输出格式

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

3 3
...
...
..#
36
4 4
....
.#..
#...
#.#.
76
5 5
.....
#..#.
..#.#
.....
..#..
154

提示

样例解释

  • 样例 11 解释:随便怎么放都是合法的。

数据范围

对于 100%100\% 的数据,保证 1n5001\le n\le 500

子任务编号 n,mn,m\le 得分
1 1 1010 17 17
2 2 100100 21 21
3 3 500500 3232