JZOJ 3831. 地图的密度

题目

Description

给出：
        整数n>r>=0，

        由0、1构成的n*n的表格f，行与列用1..n表示，第j列第i行记为f[i,j]。 
        如果[i,j]和[i',j']是表格f中的两格，则他们的距离定义为max(|i-i'|,|j-j'|)。现在需要你计算一个n*n的表格w，w[i,j](表格w中第i列第j行的数)是满足以下条件的f[x,y]的和：[x,y]与[i,j]的距离不大于r。
 
任务：
编一个程序：
        从文件MAP.IN中读入整数n、r以及表格f。
        计算表格w。
        将表格w写入文件MAP.OUT。

 

Input

    在文件MAP.IN的第一行有两个由一个空格隔开的非负整数n、r(0<=r<n<=250)。接下来的n行给出表格f。每一行包括n个数(0或1)，分别由一个空格隔开。第j+1行的第i个数表示f[i,j]。

Output

文件MAP.OUT应该包括n行。其中第j行依次给出w[1,j]...w[n,j],分别由一个空格隔开。

 

Sample Input

5 1
1 0 0 0 1
1 1 1 0 0
1 0 0 0 0
0 0 0 1 1
0 1 0 0 0
 

Sample Output

3 4 2 2 1
4 5 2 2 1
3 4 3 3 2
2 2 2 2 2
1 1 2 2 2 

 

Data Constraint

数据规模
对于100%的数据如题目。

分析

 

• 前缀和

 

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
int f[300][300],ans[300][300],sum[300][300];
int main()
{
    freopen("map.in","r",stdin);
    freopen("map.out","w",stdout);
    int n,r;
    scanf("%d%d",&n,&r);
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) scanf("%d",&f[i][j]);
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+f[i][j];
    for (int i=1;i<=n;i++) 
      for (int j=1;j<=n;j++)
      {
           int ka=max(1,i-r),kka=min(n,i+r);
           int kb=max(1,j-r),kkb=min(n,j+r);
           ans[i][j]=sum[kka][kkb]-sum[ka-1][kkb]-sum[kka][kb-1]+sum[ka-1][kb-1];
      }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
         printf("%d ",ans[i][j]);
        cout<<endl; 
    } 
      
    return 0;
}