← 返回题目列表

AtCoder · code_thanks_festival_2015_h

H. 有孔蛋糕

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

問題文

圣诞节即将来临。您决定为您的朋友制作一个洞蛋糕作为圣诞蛋糕。

制作洞洞蛋糕所用的蛋糕糊是 R 行 C 柱矩形,i (1 ≦ i ≦ R) 行 j (1 ≦ j ≦ C) 列面积 ( 我们称之为i, j)。面积( 当你吃i, j)时,C_{i,j} 你可以获得千卡。另外,面积(1, 1)是左上角,区域(R, C)是右下角。

您将按照以下步骤将蛋糕面糊加工成穿孔蛋糕。

  • 首先,4 整数 a, b, c, d (1 ≦ a < b ≦ R, 1 ≦ c < d ≦ C, b - a ≧ 2, d - c ≧ 2) 。蛋糕面糊的面积(a, c)在左上角,( 剪出右下角带有b, d) 的矩形部分。
  • 对于上一步中剪出的部分,删除边缘不存在的区域。 1 一(面积(e, f) (a+1 ≦ e ≦ b-1, c+1 ≦ f ≦ d-1) ) 并删除它,剩下的就像有洞的蛋糕一样。

此外,带孔蛋糕的卡路里摄入量是在构成带孔蛋糕的区域中确定的卡路里总值。

我注重健康的朋友说,她吃有洞的蛋糕所获得的热量只是 K 我想要一个仅含有千卡热量的蛋糕。可以计算出符合条件的可能的洞饼总数,即满足上述条件 我决定计算选择 6 整数 a, b, c, d, e, f 的方式总数。


入力

输入将以以下格式从标准输入提供。

R C K
s_1
s_2
:
s_R
  • 1 行中显示蛋糕面糊的行数。 R (3 ≦ R ≦ 350)、列数 C (3 ≦ C ≦ 350) 和您朋友的所需卡路里摄入量 K (0 ≦ K ≦ 999,999) 用空格分隔。
  • 2 从行 R 行提供有关蛋糕面糊中卡路里的信息。其中 i (1 ≦ i ≦ R) 行内长度 C 字符串 组成 s_i 。 来自行s_i 的任何字符 数量最多为 1 它们的编号最大为 9 。 从s_i 左侧开始 j (1 ≦ j ≦ C) 第一个数字是面积( 通过在穿孔蛋糕中添加i, j) 来增加卡路里含量 等于 C_{i,j} 。

出力

有洞的蛋糕总数为 1 行输出。还在输出末尾添加换行符。


入力例1

4 5 14
54311
11211
17312
11119

出力例1

2

蛋糕糊如下表所示。

5 4 3 1 1
1 1 2 1 1
1 7 3 1 2
1 1 1 1 9

例如,a = 2, b = 4, c = 1, d = 4 ,则以下区域将被剪切。

1 1 2 1
1 7 3 1
1 1 1 1

此外, 如果你按照e = 3, f = 2 打一个洞,洞蛋糕将具有以下形状(* 表示钻孔的位置)。

1 1 2 1
1 * 3 1
1 1 1 1

此时摄入的热量为1+1+2+1+1+3+1+1+1+1+1 = 14 ,满足条件。

其他 当 a = 1, b = 3, c = 3, d = 5, e = 2, f = 4 时,满足条件。


入力例2

6 7 8
1111116
1111111
1111115
1113111
1211111
1111141

出力例2

7

即使构成洞洞蛋糕的区域的卡路里排列相同,如果切口和洞的位置不同,也会被算作不同的蛋糕。


入力例3

3 3 9
211
121
112

出力例3

0

可能没有符合条件的有洞蛋糕。


入力例4

8 8 15
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111

出力例4

100