C - 広告

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400

問題文

縦に r 個、横に c 個の r×c 個のマスからなるグリッドがあり、それぞれのマスには *. が書かれています。上から i 番目、左から j 番目のマスに書かれた文字を C_{i,j} とおきます。

kenkooooさんは . のマスに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