问题描述

我们有一个包含 $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$。

示例输入 1

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

示例输出 1

4

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