← 返回题目列表

AtCoder · soundhound2018_c

C. 広告

中文机器翻译题面 查看原题

配点 : 400 点

問題文

垂直 r 件,水平 c 的 您可以创建一个包含 r×c 方格组成的网格,每个方格都有一个 * 或 . 。从上面 第 i 左起第 th j 格中写入的字符 C_{i,j} 对于

肯库奥 我决定在 . 广场上放置 SoundHound 的广告。1 在一个方格内 您只能放置 1 广告。但如果人太多的话,就会起到相反的效果,所以 2 请勿在两个广场上做广告。在这里,彼此相邻 2 两个正方形是指一个正方形以及与其上、下、左、右相邻的正方形。

kenkoooo 最多可以投放多少个广告? 包括

制約

  • 1≦r, c≦40
  • C_{i,j} 是 您也可以写 . 或 至少 * 组成

入力

输入是按以下格式从标准输入给出的。

r c
C_{1,1}C_{1,2} ... C_{1,c}
:
C_{r,1}C_{r,2} ... C_{r,c}

出力

请输出kenkoooo可以运行的最大广告数量。


入力例 1

3 3
...
...
...

出力例 1

5

放置广告 如果我们将其表示为 # ,我们得到以下结果 5 您可以投放一个广告。

#.#
.#.
#.#

入力例 2

2 2
**
**

出力例 2

0

不幸的是,1 有时您无法投放广告。


入力例 3

1 1
.

出力例 3

1

入力例 4

3 4
*..*
..**
*...

出力例 4

4