题目描述

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

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

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

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

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

输入格式

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

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

输出格式

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

题目大意

题目描述

给定一个 $h$ 行 $w$ 列的网格图，图中的每个格子不是#就是.。

若当前处于静止状态，可以向四个方向中的任意一个移动，直到到达网格图边界或到达一个为#的格子时才可停止。

将图中上起第 $r$ 行左起第 $c$ 列的格子记为 $(r,c)$。“从 $(r,c)$ 来看，可以满足目的”的条件是：从 $(r,c)$ 出发，通过以上形式的移动，在移动若干次以后能够访问到图中的所有格子。

问最少改变多少个.格子为#格子才能满足：从任意一个格子来看，都能满足目的？

输入格式

第一行输入两个整数 $h,w$。

接下来 $h$ 行，每行一个长度为 $w$，仅有#和.的字符串。

输出格式

一行一个整数，最少需要改变的格子数量。

说明/提示

数据规模与约定

$2\le h,w\le 1000$。

样例 #1 解释

将格子 $(2,2)$ 改成#即可。

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

1

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

6

提示

制約

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

Sample Explanation 1

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