题目描述

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

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

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

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

输入格式

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

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

输出格式

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

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

1

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

6

说明/提示

数据规模与约定

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

样例 #1 解释

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