CodeForces 372B. Counting Rectangles is Fun

20386053

浏览: 461432 次

最近访客更多访客>>

u012363178

wangyy

chuan518

iidioter

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (936)

社区版块

存档分类

2013-12 ( 121)
2013-11 ( 163)
2013-10 ( 64)
更多存档...

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

Let's define a "rectangle" as four integersa, 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 followingqqueries: 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,mandq(1 ≤ n, m ≤ 40, 1 ≤ q ≤ 3·105). Each of the nextnlines containsmcharacters — 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 nextqlines 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 a5 × 5rectangular grid, and the first, the second, and the third queries are represented in the following image.

$\text{[math]}$

For the first query, there are10good rectangles, five1 × 1, two2 × 1, two1 × 2, and one1 × 3.
For the second query, there is only one1 × 1good rectangle.
For the third query, there are7good rectangles, four1 × 1, two2 × 1, and one3 × 1.

4D consecutive sums 涨姿势了。。。

#include <iostream>
#include <cstring>
#include <cstdio>

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<x;i++)
    {
        scanf("%s",str);
        for(int j=0;j<y;j++)
        {
            m[i][j]=str[j]-'0';
        }
    }
    for(int i=0;i<x;i++)
    {
        for(int j=0;j<y;j++)
        {
            rui[i+1][j+1]=rui[i+1][j]+rui[i][j+1]-rui[i][j]+m[i][j];
        }
    }
    for(int i=0;i<x;i++)
    {
        for(int j=0;j<y;j++)
        {
            for(int k=i;k<x;k++)
            {
                for(int l=j;l<y;l++)
                {
                    if(rui[k+1][l+1]+rui[i][j]-rui[i][l+1]-rui[k+1][j]==0)
                    {
                        det[i][j][k][l]=1;
                    }
                }
            }
        }
    }
    for(int i=0;i<x;i++)
    {
        for(int j=0;j<y;j++)
        {
            for(int k=0;k<x;k++)
            {
                for(int l=0;l<y;l++)
                {
                    ans[i+1][j+1][k+1][l+1]
                    =ans[i][j+1][k+1][l+1]
                    +ans[i+1][j][k+1][l+1]
                    +ans[i+1][j+1][k][l+1]
                    +ans[i+1][j+1][k+1][l]
                    -ans[i][j][k+1][l+1]
                    -ans[i][j+1][k][l+1]
                    -ans[i][j+1][k+1][l]
                    -ans[i+1][j][k][l+1]
                    -ans[i+1][j][k+1][l]
                    -ans[i+1][j+1][k][l]
                    +ans[i+1][j][k][l]
                    +ans[i][j+1][k][l]
                    +ans[i][j][k+1][l]
                    +ans[i][j][k][l+1]
                    -ans[i][j][k][l]
                    +det[i][j][k][l];
                }
            }
        }
    }
    while(q--)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        a--; b--; c--; d--;
        printf("%d\n",
               ans[c+1][d+1][c+1][d+1]
               -ans[a][d+1][c+1][d+1]
               -ans[c+1][b][c+1][d+1]
               -ans[c+1][d+1][a][d+1]
               -ans[c+1][d+1][c+1][b]
               +ans[a][b][c+1][d+1]
               +ans[a][d+1][a][d+1]
               +ans[a][d+1][c+1][b]
               +ans[c+1][b][a][d+1]
               +ans[c+1][b][c+1][b]
               +ans[c+1][d+1][a][b]
               -ans[c+1][b][a][b]
               -ans[a][d+1][a][b]
               -ans[a][b][c+1][b]
               -ans[a][b][a][d+1]
               +ans[a][b][a][b]
               );
    }
    return 0;
}

一种更加简洁的写法。。。。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int n, m, q, sum[50][50], ct[50][50][50][50];
char map[50][50];

int main()
{
	cin >> n >> m >> q;
	for (int i = 0; i < n; i++)
	{
		cin >> map[i];
	}
	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = m - 1; j >= 0; j--)
		{
			sum[i][j] = sum[i + 1][j] + sum[i][j + 1] - sum[i + 1][j + 1] + (map[i][j] == '1');
		}
	}
	for (int x1 = n - 1; x1 >= 0; x1--)
	{
		for (int x2 = x1 + 1; x2 <= n; x2++)
		{
			for (int y1 = m - 1; y1 >= 0; y1--)
			{
				for (int y2 = y1 + 1; y2 <= m; y2++)
				{
					int &c = ct[x1][y1][x2][y2];
					c = ct[x1 + 1][y1][x2][y2]
						+ ct[x1][y1 + 1][x2][y2]
						+ ct[x1][y1][x2 - 1][y2]
						+ ct[x1][y1][x2][y2 - 1]

						- ct[x1][y1][x2 - 1][y2 - 1]
						- ct[x1][y1 + 1][x2][y2 - 1]
						- ct[x1][y1 + 1][x2 - 1][y2]
						- ct[x1 + 1][y1][x2][y2 - 1]
						- ct[x1 + 1][y1][x2 - 1][y2]
						- ct[x1 + 1][y1 + 1][x2][y2]

						+ ct[x1][y1 + 1][x2 - 1][y2 - 1]
						+ ct[x1 + 1][y1][x2 - 1][y2 - 1]
						+ ct[x1 + 1][y1 + 1][x2][y2 - 1]
						+ ct[x1 + 1][y1 + 1][x2 - 1][y2]

						- ct[x1 + 1][y1 + 1][x2 - 1][y2 - 1];
					if (sum[x1][y1] - sum[x1][y2] - sum[x2][y1] + sum[x2][y2] == 0) c++;
				}
			}
		}
	}
	while (q--)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		a--; b--;
		cout << ct[a][b][c][d] << endl;
	}
	return 0;
}

分享到：