画圈游戏

题号：NC236756
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Playf在玩画圈游戏。Playf有一张大小为 $n\times m$ 的方格图，其中有一些方格被涂上了星星的图案。Playf可以在方格内画圈，每个圈只能覆盖相邻的两个方格。Playf想要让每一个有星星图案的方格都被他画的圈覆盖，他至少要画多少个圈。

定义两个方格是相邻的，当且仅当它们有一条公共的边。

第一行输入两个整数  ，表示方格图的大小。
接下来  行，每行输入  个字符，描述了这个方格图。其中字符'*'表示被涂上星星图案的方格，字符'o'表示空白方格。

输出一行一个整数，表示Playf最少需要画的圆圈个数。

示例1

复制

2 4
**o*
o**o

复制

示例2

复制

7 9
ooo**oooo
**oo*ooo*
o*oo**o**
ooooooooo
*******oo
o*o*oo*oo
*******oo

复制