多边形

题目描述

有一个 $H$ 行 $W$ 列的网格。从上数第 $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

用网格左上、左下、右上、右下的角分别为 $(0, 0), (H, 0), (0, W), (H, W)$ 的坐标系表示时，给定的图形是以 $(1, 1), (4, 1), (4, 4), (1, 4)$ 为顶点的 $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}$ 是 .
• 涂黑的部分是一个没有自交的多边形