分数: 425 点
问题陈述
有一个 H \times W 网格,每个单元格包含一个整数 0 or 1.
每个单元格中写入的整数信息如下 H 字符串 S_1, S_2, \dots, S_H 长度 W。
如果 j- 第一个字符 S_i is 0,那么 0 写入位于 i从顶部开始的第行和 j- 网格左侧的第列;如果 j- 第一个字符 S_i is 1,那么 1 写入该单元格中。
找出写入的整数之和等于的矩形区域的数量 K.
更正式地说,求整数四元组的个数 (r_1, c_1, r_2, c_2) 满足以下所有条件:
- 1 \le r_1 \le r_2 \le H
- 1 \le c_1 \le c_2 \le W
- 写入单元格中的整数之和 i从顶部开始的第行和 j- 从左侧算起的所有整数对上的第列 (i, j) 满意 r_1 \le i \le r_2, c_1 \le j \le c_2,等于 K.
约束
- H 和 W 是介于 1 和 500,包括在内。
- K 是介于 0 和 HW,包括在内。
- S_i 是一个长度为的字符串 W 组成
0和1.
输入
输入由标准输入按以下格式给出:
H W K S_1 S_2 \vdots S_H
输出
输出答案。
示例输入 1
3 4 3 1001 1101 0110
示例输出 1
8
有八个矩形区域,其中写入的整数之和等于 K:
- 从行中提取的矩形区域 1 到行 2 从顶部和列 1 转至专栏 2 从左起
- 从行中提取的矩形区域 1 到行 2 从顶部和列 1 转至专栏 3 从左起
- 从行中提取的矩形区域 1 到行 2 从顶部和列 2 转至专栏 4 从左起
- 从行中提取的矩形区域 1 到行 3 从顶部和列 2 转至专栏 3 从左起
- 从行中提取的矩形区域 1 到行 3 从顶部和列 3 转至专栏 4 从左起
- 从行中提取的矩形区域 2 到行 2 从顶部和列 1 转至专栏 4 从左起
- 从行中提取的矩形区域 2 到行 3 从顶部和列 1 转至专栏 2 从左起
- 从行中提取的矩形区域 2 到行 3 从顶部和列 2 转至专栏 3 从左起
示例输入 2
5 4 20 0101 1010 0101 1010 0101
示例输出 2
0
示例输入 3
15 20 17 10111101101100000100 01100000000010000011 01110010111000111000 11001100000111011000 10100001100011100010 01101000101010000101 10110001111110000100 10110011101100101101 01010001110011001001 01010110010001100110 01110100011110011110 01100000100111010010 11001101100111101100 10111100010101111011 00101101011100010000
示例输出 3
448