分数: 300 点
问题陈述
我们有一个网格 H 行和 W 列。让 (i, j) 是位于 i从顶部数第行和 j左起第 列。
每个方块都漆成黑色或白色。如果 S_{i, j} is #, (i, j) 被漆成黑色;如果 S_{i, j} is ., (i, j) 被漆成白色。
保证最外面的方块是白色的。也就是说,正方形可以表示为 (1, j), (H, j), (i, 1),或 (i, W) 是白色的。
将网格中涂成黑色的部分视为多边形。它(至少)有多少条边?
这里保证涂黑的部分形成无自交的多边形,即满足以下条件:
- 至少一个方块被漆成黑色;
- 我们可以通过反复向上、向下、向左或向右移动,在任意两个涂成黑色的方块之间移动,同时仅穿过黑色方块;
- 我们可以通过重复向上、向下、向左或向右移动,同时只穿过白色方块,在任意两个涂成白色的方块之间移动。 (请注意,网格中最外面的方块都漆成白色。)
约束
- 3 \le H \le 10
- 3 \le W \le 10
- S_{i, j} is
#or.. - 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-gon。
示例输入 1
5 5 ..... .###. .###. .###. .....
示例输出 1
4
如果我们使用网格的左上角、左下角、右上角和右下角的坐标系 (0, 0), (H, 0), (0, W),和 (H, W),给定的图形是一个四边形,其顶点是 (1, 1), (4, 1), (4, 4),和 (1, 4).