Digital Graffiti

题目描述

我们有一个 $H$ 行 $W$ 列的网格。令 $(i, j)$ 为从上往下第 $i$ 行、从左往右第 $j$ 列的方格。
每个方格被涂成黑色或白色。如果 $S_{i, j}$ 是 #，则 $(i, j)$ 被涂成黑色；如果 $S_{i, j}$ 是 $.$，则 $(i, j)$ 被涂成白色。
保证最外侧的方格是白色。也就是说，可以表示为 $(1, j)$、$(H, j)$、$(i, 1)$ 或 $(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

提示

$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}$ 是 $.$。 被涂成黑色的部分构成一个无自交的多边形。如果我们使用一个坐标系，其中网格的左上、左下、右上和右下角分别是 $(0, 0)$、$(H, 0)$、$(0, W)$ 和 $(H, W)$，则给定的图形是一个顶点为 $(1, 1)$、$(4, 1)$、$(4, 4)$ 和 $(1, 4)$ 的四边形。

标签: AtCoder|abc191C

来源

AtCoder|abc191C