AT_abc018_3 [ABC018C] 菱型カウント

[problemUrl]: https://atcoder.jp/contests/abc018/tasks/abc018_3 縦 $ R $ 行、横 $ C $ 列の長方形領域がある。上から $ i\ (1\ ≦\ i\ ≦\ R) $ 行目、左から $ j\ (1\ ≦\ j\ ≦\ C) $ 列目にあるマスをマス ($ i $, $ j $) と呼ぶことにする。これらのマスのうちいくつかのマスは黒く、他のマスは白く塗られている。 また、ある整数 $ K $ が定められている。 ここで、以下の条件を満たすように新たに緑色を塗ることを考える。この操作は1 回だけ行う。 - ある整数 の組 $ x\ (K\ ≦\ x\ ≦\ R\ -\ K\ +\ 1) $, $ y\ (K\ ≦\ y\ ≦\ C\ -\ K\ +\ 1) $ に対して、|$ i-x $|+|$ j-y $|$ ≦\ K\ -\ 1 $ を満たすすべてのマス ($ i $,$ j $) について、マス ($ i $,$ j $) は元々白いマスで、かつ、この操作で緑色に塗られる。さらに、|$ i-x $|+|$ j-y $|$ ≧\ K $ を満たすすべてのマスについて、そのマスは緑色に塗らない。 このような色の塗り方の総数はいくらか。ただし、ここでいう塗り方とは、どのマスがどの色になったかという組み合わせのことで、色の塗る順番は考慮しないものとする。

入力は以下の形式で標準入力から与えられる。 > $ R $ $ C $ $ K $ $ s_1 $ $ s_2 $ : $ s_R $ - $ 1 $ 行目には、$ 3 $ つの整数 $ R\ (3\ ≦\ R\ ≦\ 500) $, $ C\ (3\ ≦\ C\ ≦\ 500) $, $ K\ (2\ ≦\ K\ ≦\ 500) $ が空白区切りで書かれている。これは、長方形領域が縦 $ R $ 行、横 $ C $ 列あることを表す。$ K $ は文中で定められた整数である。 - $ 2 $ 行目から $ R $ 行には、マスに関する情報が与えられる。$ R $ 行のうち $ i\ (1\ ≦\ i\ ≦\ R) $ 行目には、長さ $ C $ の文字列 $ s_i $ が与えられる。文字列 $ s_i $ は `o`, `x` の $ 2 $ 種類の文字でのみ構成されており、$ s_i $ の左から $ j\ (1\ ≦\ j\ ≦\ C) $ 文字目の文字が `o` ならマス ($ i $,$ j $) が白いマスであることを、`x` ならマス ($ i $,$ j $) が黒いマスであることを表す。

緑色の塗り方の総数を $ 1 $ 行に出力せよ。出力の末尾に改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ R\ ≦\ 50 $ かつ $ C\ ≦\ 50 $ を満たすデータセット $ 1 $ に正解した場合は、$ 30 $ 点が与えられる。 ### Sample Explanation 1 以下の $ 3 $ 通りが考えられます (`o` は白いマス、`x` は黒いマス、`\*` は緑色のマスを表します)。 x\\\*ooo\\\*\\\*\\\*oxo\\\*ooooxxoo xo\\\*ooo\\\*\\\*\\\*xoo\\\*oooxxoo xooooooo\\\*xoo\\\*\\\*\\\*oxx\\\*o