C - 数字涂鸦

分数: $300$ 分

题目描述

我们有一个 $H$ 行 $W$ 列的格子。设 $(i, j)$ 表示从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子。
每个格子要么是黑色，要么是白色。如果 $S_{i, j}$ 是 #，则 $(i, j)$ 是黑色；如果 $S_{i, j}$ 是 .，则 $(i, j)$ 是白色。
可以保证最外层的格子都是白色的。也就是说，可以表示为 $(1, j)$、$(H, j)$、$(i, 1)$ 或 $(i, W)$ 的格子都是白色的。

将被涂成黑色的格子部分看作一个多边形。它至少有多少条边？

题目保证被涂成黑色的部分是一个没有自相交的多边形，即满足以下条件：

• 至少有一个格子被涂成黑色；
• 我们只能通过上下左右的移动，经过黑色的格子，从一个被涂成黑色的格子移动到另一个被涂成黑色的格子；
• 我们只能通过上下左右的移动，经过白色的格子，从一个被涂成白色的格子移动到另一个被涂成白色的格子。（注意，格子的最外层都是白色的。）

约束

• $3 \le H \le 10$
• $3 \le W \le 10$
• $S_{i, j}$ 是 # 或 .。
• $S_{1, j}$ 和 $S_{H, j}$ 是 .。
• $S_{i, 1}$ 和 $S_{i, W}$ 是 .。
• 被涂成黑色的部分是一个没有自相交的多边形。

输入

输入在标准输入中给出，格式如下：

$H$ $W$

$S_{1, 1} S_{1, 2} S_{1, 3} \dots S_{1, W}$

$S_{2, 1} S_{2, 2} S_{2, 3} \dots S_{2, W}$

$S_{3, 1} S_{3, 2} S_{3, 3} \dots S_{3, W}$

$\hspace{40pt} \vdots$

$S_{H, 1} S_{H, 2} S_{H, 3} \dots S_{H, W}$

输出

输出一个整数 $n$，表示被涂成黑色的部分可以看作一个 $n$ 边形。

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

4

如果我们使用一个坐标系，其中格子的左上角、左下角、右上角和右下角分别为 $(0, 0)$、$(H, 0)$、$(0, W)$ 和 $(H, W)$，给出的图形是一个四边形，其顶点为 $(1, 1)$、$(4, 1)$、$(4, 4)$ 和 $(1, 4)$。