滑冰场

时间限制：2s
空间限制：1024MB

题目描述

有一个由 $H$ 行 $W$ 列方格组成的滑冰场。从北向南第 $r$ 行、从西向东第 $c$ 列的方格记为 $(r,c)$。每个方格是冰面或地面：当 $S_{r,c}$ 为 # 时，它是地面；当 $S_{r,c}$ 为 . 时，它是冰面。滑冰场的四周都是墙壁。

当高桥静止在某个方格时，他可以选择向东、西、南、北中的一个方向开始移动。开始移动后，他会一直沿同一方向前进，直到撞上墙壁，或到达一格地面并停下；如果开始移动的方格本身是地面，则这格地面不会使他立刻停下。

如果从方格 $(r,c)$ 静止出发，能够通过若干次移动经过滑冰场的每一个方格，就称这个滑冰场对于 $(r,c)$ 是无浪费的。这里只要求经过每个方格，不要求在每个方格上停下。

高桥可以把若干个冰面方格改成地面方格。他希望修改后，滑冰场对于每一个方格都是无浪费的。求至少需要修改多少个方格。

输入格式

第一行输入两个整数 $H,W$。

接下来 $H$ 行，每行一个长度为 $W$ 的字符串 $S_r$，描述滑冰场的第 $r$ 行。

输出格式

输出一个整数，表示至少需要修改的方格数。

样例输入 1

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

样例输出 1

1

样例输入 2

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

样例输出 2

6

数据范围

对于所有测试数据，满足 $2\le H,W\le 1000$，且 $S_{r,c}$ 只可能是 # 或 .。