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

题目背景

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

题目描述

有一面 $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$。

子任务编号	$n,m\le$	得分
$1$	$10$	$17$
$2$	$100$	$21$
$3$	$500$	$32$

#5724. 「COCI 2024/2025 #5」Zid

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #5 T2「Zid」

Mr. Malnar 想要在墙上挂一张他自己的照片。墙面可以表示为一个 $n$ 行 $m$ 列的矩阵。由于他以前曾多次在墙上挂照片，某些位置至今仍留有嵌入的钉子。这些位置用符号 # 标记，而空位则用符号 . 标记。

照片呈长方形，尺寸可以任意，挂在墙上时会覆盖一个矩形区域。若照片覆盖的含有钉子的位置不超过一个，则该照片可以放置在墙上。

请帮 Mr. Malnar 计算他可以将照片挂在墙上的不同方式的总数。

输入格式

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 500)$，代表墙面的尺寸。

接下来的 $n$ 行中，每行包含 $m$ 个字符 $c_{ij}$，描述了墙面的情况。每个字符要么是 .，要么是 #。

输出格式

在一行中输出将照片挂在墙上的可能方式总数。

样例 1

输入

3 3
...
...
..#

输出

36

样例 2

输入

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

输出

76

只要照片覆盖的钉子不超过一个，每种放置方式都是发合法的。

样例 3

输入

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

输出

154

照片的放置方式不能使其同时覆盖位置 $(3, 1)$ 和 $(4, 1)$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$17$	$n, m \leq 10$
$2$	$21$	$n, m \leq 100$
$3$	$32$	无附加限制