题目描述

$H$ 行 $W$ 列のマス目があります。このマス目の、上から $i$ 番目、左から $j$ 番目のマスを、マス $(i,\ j)$ と呼ぶことにします。
各マスは黒または白に塗られています。$S_{i,\ j}$ が # ならばマス $(i,\ j)$ は黒に塗られており、. ならば白に塗られています。
マス目の一番外側のマス、すなわち $(1,\ j),\ (H,\ j),\ (i,\ 1),\ (i,\ W)$ のいずれかの形で表されるマスは白に塗られていることが保証されます。

黒に塗られた部分を多角形として見たとき、これが (最小で) 何角形になるかを求めてください。

ここで、黒に塗られた部分は一つの自己交叉のない多角形となることが保証されます。すなわち、以下のことが保証されます。

• 黒に塗られたマスが少なくとも一つ存在する
• 黒に塗られた任意の $2$ マスは、辺を共有するマスへの移動を繰り返し、黒に塗られたマスのみを通って互いに到達可能である
• 白に塗られた任意の $2$ マスは、辺を共有するマスへの移動を繰り返し、白に塗られたマスのみを通って互いに到達可能である(マス目の一番外側のマスは全て白に塗られていることに注意してください)

输入格式

入力は以下の形式で標準入力から与えられる。

$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$ を出力せよ。

题目大意

题目描述

有一个 $H$ 行 $W$ 列的表格，格子要么为黑色，用‘#’表示，要么为白色，用‘.’表示。第一行和最后一行，第一列和最后一列都是白色格子。 考虑黑色部分组成的多边形，问多边形有多少条边？ 保证表格中，黑色部分为四联通区域，白色部分也为四联通区域。所谓四联通，即通过上、下、左、右四个方向，可以访问所有格子。 表格中至少存在一个黑色格子。

输入格式

第一行两个整数 $H$ , $W$ . 接下来 $H$ 行，每行一个长度为 $W$ 的字符串，由'#'或'.'组成。

输出格式

一个整数，表示答案

数据范围与提示

$3 \leq H \leq 10, 3 \leq W \leq 10$

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}$ は .
• 黒に塗られた部分は一つの自己交叉のない多角形となる

Sample Explanation 1

マス目の左上、左下、右上、右下の隅をそれぞれ $(0,\ 0),\ (H,\ 0),\ (0,\ W),\ (H,\ W)$ とする座標系で表すと、与えられる図形は $(1,\ 1),\ (4,\ 1),\ (4,\ 4),\ (1,\ 4)$ を頂点とする $4$ 角形です。