← 返回题目列表

AtCoder · abc018_3

C. 菱形计数

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

問題文

縦 R 行、横 C 我有一个矩形区域的列。从上面 i (1 ≦ i ≦ R) 行,从左起 j (1 ≦ j ≦ C) 选择列中的单元格 ( 我们将其称为i, j)。其中一些方块被漆成黑色,另一些被漆成白色。

另外,一些整数 K 已定义。

现在,考虑绘制新的绿色,以满足以下条件。仅执行此操作一次。

  • 一组整数 对于 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*ooo
***ox
o*ooo
oxxoo

xo*oo
o***x
oo*oo
oxxoo

xoooo
ooo*x
oo***
oxx*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