H: 板

問題

$R * C$ のマスが与えられます．各マスは何もないマスか，穴が開いているマスのどちらかです． 与えられるマスは以下の条件を満たします。

• 穴の開いたマス同士は連結である．（穴の開いたマスを十字方向につたって任意の穴の開いたマスに移動することができる）
• 何もないマス同士は連結である．

あなたは幅が $1$ の任意長の長方形型のタイルを生成することができます． このタイルを複数枚設置して全ての穴のあるマスを埋めたいです．タイルを設置するとき，以下の制約を守る必要があります．

• タイルは縦向きか横向きの $2$ 方向でのみ設置が可能である．
• 一つのマスに二枚以上のタイルが重なるように設置してはいけない．
• 穴のないマスの上にタイルがあってはいけない．

上記の制約を守って全ての穴のあるマスをタイルで埋めたときの，タイルの最小枚数を答えてください．

制約

• $1 \leq R, C \leq 25$
• $|S_i| = C \ \ \ \ |S_i|$ は文字列の長さを表す。
• $S_{i,j}$ は '#' または '.' で、それぞれ穴の開いたマス、何もないマスを表す。

入力形式

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

$R\ C$
$S_{1,1} \dots S_{1,C}$
$\vdots$
$S_{R,1} \dots S_{R,C}$

出力

最小回数を出力してください。末尾に改行も出力してください。

サンプル

サンプル入力 1

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

サンプル出力 1

3

$3$ 枚のタイルを以下のように置くのが最適です

.....
.1.3.
.123
.1.3
.....

サンプル入力 2

4 10
##########
....#.....
....#.....
..........

サンプル出力 2

2

$2$ 枚のタイルを以下のように置くのが最適です．タイルの長さは任意長にでき，縦向きにも横向きにも使えることに注意してください．

1111111111
....2.....
....2.....
..........

Note

Commentary

 

---