配点 : $600$ 点

問題文

高橋くんは $H$ 行 $W$ 列のマスからなるスケートリンクにいます。 北から $r$ 行目、西から $c$ 列目をマス $(r, c)$ と表すことにします。 各マスは氷または地面であり、マス $(r, c)$ は $S_{r, c}$ が # であるときは地面、. であるときは氷です。 スケートリンクの外側は壁で覆われています。

高橋くんは、スケートリンク上で静止しているとき、東西南北のいずれかに移動を開始することができます。 移動開始後、高橋くんは同じ方向に動き続け、壁にぶつかるか、（移動を開始したマス以外の）地面のマスの 上 にたどりついたときに静止します。

以下の条件を満たす時、「 マス $(r, c)$ から見て、スケートリンクは無駄がない」と言います:

• 高橋くんがマス $(r, c)$ で静止している状態から、うまく移動を繰り返すことによって、全てのマスを 通過 することができる。（各マスの上で静止できるかどうかは問わない。）

高橋くんはどのマスから見てもスケートリンクに無駄がないようにするために、いくつかの氷のマスを地面のマスに変更したいです。 最小でいくつのマスを変更すればよいか求めてください。

制約

• $2\le H,W \le 1000$
• $S_{r,c}$ は # または .

入力

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

$H$ $W$

$S_{1,1}\dots S_{1,W}$

$\vdots$

$S_{H,1}\dots S_{H,W}$

出力

どのマスから見てもスケートリンクに無駄がないようにするために変更する必要のあるマスの数の最小値を出力せよ。

3 9
.........
.........
.........

1

最初の状態では、マス $(1,1)$ から始めてマス $(2,2)$ を通過することができません。 例えば以下のように変更すれば条件を満たせます。

.........
........#
.........

10 10
..........
#...#.....
..........
..........
..........
....#.....
.#......#.
..........
..........
..........

6