频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
CodeForces 372B. Counting Rectangles is Fun
2013-12-17 11:31:53      个评论    来源:码代码的猿猿  
收藏   我要投稿


B. Counting Rectangles is Fun time limit per test 4 seconds memory limit per test 256 megabytes input standard input output standard output

There is an n?×?m rectangular grid, each cell of the grid contains a single integer: zero or one. Let's call the cell on the i-th row and thej-th column as (i,?j).

Let's define a "rectangle" as four integers a,?b,?c,?d (1?≤?a?≤?c?≤?n; 1?≤?b?≤?d?≤?m). Rectangle denotes a set of cells of the grid{(x,?y) :? a?≤?x?≤?c,?b?≤?y?≤?d}. Let's define a "good rectangle" as a rectangle that includes only the cells with zeros.

You should answer the following q queries: calculate the number of good rectangles all of which cells are in the given rectangle.

Input

There are three integers in the first line: n, m and q (1?≤?n,?m?≤?40,?1?≤?q?≤?3·105). Each of the next n lines contains m characters — the grid. Consider grid rows are numbered from top to bottom, and grid columns are numbered from left to right. Both columns and rows are numbered starting from 1.

Each of the next q lines contains a query — four integers that describe the current rectangle, a, b, c, d (1?≤?a?≤?c?≤?n; 1?≤?b?≤?d?≤?m).

Output

For each query output an answer — a single integer in a separate line.

Sample test(s) input
5 5 5
00101
00000
00001
01000
00001
1 2 2 4
4 5 4 5
1 2 5 2
2 2 4 5
4 2 5 3
output
10
1
7
34
5
input
4 7 5
0000100
0000010
0011000
0000000
1 7 2 7
3 1 3 1
2 3 4 5
1 2 2 7
2 2 4 7
output
3
1
16
27
52
Note

For the first example, there is a 5?×?5 rectangular grid, and the first, the second, and the third queries are represented in the following image.

\

  • For the first query, there are 10 good rectangles, five 1?×?1, two 2?×?1, two 1?×?2, and one 1?×?3.
  • For the second query, there is only one 1?×?1 good rectangle.
  • FZ喎"/kf/ware/vc/" target="_blank" class="keylink">vciB0aGUgdGhpcmQgcXVlcnksIHRoZXJlIGFyZSA3IGdvb2QgcmVjdGFuZ2xlcywgZm91ciAxP6HBPzEsIHR3byAyP6HBPzEsCiBhbmQgb25lIDM/ocE/MS4KPHA+CjwvcD4KCgoKCgo0RCBjb25zZWN1dGl2ZSBzdW1zINXH18vKxsHLoaOho6GjPGJyPgo8cD48L3A+CjxwPjxwcmUgY2xhc3M9"brush:java;">#include #include #include using namespace std; int m[50][50]; int rui[50][50]; int det[50][50][50][50]; int ans[50][50][50][50]; int x,y,q; char str[50]; int main() { scanf("%d%d%d",&x,&y,&q); for(int i=0;i



点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:FZU2132 - LQX的作业(概率论)
下一篇:LeetCode Unique Paths II
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站