[POI2000]密度图

Grade 0 Open Time Tuesday, 22 January 2013, 11:10 am
Discount 0.8 Time Discount Tuesday, 22 January 2013, 11:10 am
Allow late Yes Close Time Tuesday, 22 January 2013, 11:10 am
Input file mdt.in Output file mdt.out

问题描述

      在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<=R

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

输出文件

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

样例输入

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

样例输出

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