可以看出，这道题就是求以每个点位中心，边长为2r+1的矩阵的和。最简单的方法就是对于NN个点，每个点都以RR的时间复杂度求出矩阵的和，总时间复杂度为O(N^2R^2)。其实许多次的计算都是冗余的，我们可以类比求最大子矩阵的方法，充分利用已有的值，快速求出矩阵的和。

首先把二维的矩阵压缩为一个一维的序列，即把每k列以第i行为中心[i-r,i+r]的和算出，保存在S[k]中。然后求以第j个位中心，S[k-r]..S[k+r]的和Sum，Sum的值就是对应的W[i,j]的值。当求W[i,j+1]的值时，就不必再重新全部计算，只需考虑它与W[i,j]的增量，即W[i,j+1]=W[i,j]+S[j+r+1]-S[j-r-1]。当换行的时候，只需计算W[i,1]的值即可。这样，由每一行的第一个值推出这一行的所有值，可以大大缩短时间。时间复杂度为O(N^2)，于是完美地解决了这个问题。

/* 
 * Problem: POI2001 map
 * Author: Guo Jiabao
 * Time: 2009.1.5 21:42
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAX=252;

int N,r;
int A[MAX][MAX];
int S[MAX];

void init()
{
	freopen("map.in","r",stdin);
	freopen("map.out","w",stdout);
	scanf("%d%d",&N,&r);
	for (int i=1;i<=N;i++)
		for (int j=1;j<=N;j++)
			scanf("%d",&A[i][j]);
}

void solve()
{
	int i,j,a,b,U;
	a=1;
	if ((b=1+r)>N) b=N;
	for (i=1;i<=N;i++)
	{
		S[i]=0;
		for (j=a;j<=b;j++)
			S[i]+=A[j][i];
	}
	for (i=1;i<=N;i++)
	{
		if (i>1)
		{
			for (j=1;j<=N;j++)
			{
				if (i-r-1>=1)
					S[j]-=A[i-r-1][j];
				if (i+r<=N)
					S[j]+=A[i+r][j];
			}
		}
		U=0;
		for (j=a;j<=b;j++)
			U+=S[j];
		printf("%d",U);
		for (j=2;j<=N;j++)
		{
			if (j-r-1>=1)
				U-=S[j-r-1];
			if (j+r<=N)
				U+=S[j+r];
			printf(" %d",U);
		}
		putchar('n');
	}
}

int main()
{
	init();
	solve();
	return 0;
}

<h2><span class="mw-headline">密度图 </span></h2>

问题描述

在ByteLand上有一块地区，蕴藏了ByteLand上最珍贵的Bit矿物质。科学家们将这块地区划分成了N×N个相同大小的单元格， 并对每个单元格进行了考察研究：有的单元格中有丰富的Bit矿物质——科学家用1来标识；有的单元格蕴藏的矿物质很少——科学家用0来标识。

假设用W(i,j)和F(i’,j’)来分别表示两个单元格。那么它们之间的距离被定义为：max(|i - i'|, |j - j'|)，例如W(1,3)和F(4,2)的距离为3。

鉴于可持续发展的思想和开采能力的限制，ByteLand当局计划以一块单元格为中心，开采与中心距离不超过R的所有单元格内的矿藏。为了选定一个合适的单元格作中心，当局希望能够预先了解：以任意一个单元格为中心时，开采量的情况。

于是，当局将一张矿藏地图交给你，上面的N×N个单元格中包含数字0或1。你被要求根据这张矿藏地图，绘制出相应的“矿藏密度图”，分别以每块单元格为中心，计算与中心距离不超过R的所有标识为1的单元格个数。

输入文件

第一行有两个数字N和R（0&lt;=R&lt;N&lt;=250）。

以下N行，每行N个数字。第i+1行第j个数字为单元格(i,j)的标识——0或1。

输出文件

输出文件有N行，每行N个数字。第i行第j个数字表示：与(i,j)距离不超过R的所有标识为1的单元格个数。

样例输入
<pre>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</pre>
样例输出
<pre>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</pre>

上次修改时间 2017-02-03