C - 菱型カウント
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
縦 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) が黒いマスであることを表す。
部分点
この問題には部分点が設定されている。
- R ≦ 50 かつ C ≦ 50 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
出力
緑色の塗り方の総数を 1 行に出力せよ。出力の末尾に改行を入れること。
入力例1
4 5 2 xoooo oooox ooooo oxxoo
出力例1
3
以下の 3 通りが考えられます (o は白いマス、x は黒いマス、* は緑色のマスを表します)。
| x | * | o | o | o |
| * | * | * | o | x |
| o | * | o | o | o |
| o | x | x | o | o |
| x | o | * | o | o |
| o | * | * | * | x |
| o | o | * | o | o |
| o | x | x | o | o |
| x | o | o | o | o |
| o | o | o | * | x |
| o | o | * | * | * |
| o | x | x | * | o |
入力例2
4 5 2 ooooo oxoox oooox oxxoo
出力例2
0
入力例3
8 6 3 oooooo oooooo oooooo oooooo oxoooo oooooo oooooo oooooo
出力例3
4