← 返回题目列表

AtCoder · abc191_c

C. 数字涂鸦

中文机器翻译题面 查看原题

分数: 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).