#P11752. [COCI 2024/2025 #5] 挂画 / Zid
[COCI 2024/2025 #5] 挂画 / Zid
题目背景
译自 COCI 2024/2025 #5 T2。。满分为 。
题目描述
有一面 行 列的矩形墙,被划分为 个区域。墙上有些区域有钉子,用 表示;其他的区域没有钉子,用 。
现在要在墙上挂画。我们说一种挂画方式是合法的,当且仅当:
- 画占据墙上的一个矩形区域;
- 画占据的区域中至多一个区域存在钉子。
求出有多少种合法的挂画方式。
输入格式
第一行,两个正整数 。
接下来 行,第 行一个字符串 , 表示墙上第 行第 列的区域的状态。
输出格式
输出一行一个正整数表示答案。
3 3
...
...
..#
36
4 4
....
.#..
#...
#.#.
76
5 5
.....
#..#.
..#.#
.....
..#..
154
提示
样例解释
- 样例 解释:随便怎么放都是合法的。
数据范围
对于 的数据,保证 。
子任务编号 | 得分 | |
---|---|---|