TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3137
  • 题目
  • P3137丢炸弹
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    何老板最近迷上了一款驾驶轰炸机投炸弹的小游戏。该游戏的地图是一个n*m的方格矩阵。每个方格都上有一个数字,代表该方格里怪兽的数量。
    何老板操控的轰炸机只有一枚炸弹,该炸弹的杀伤半径为R,他可以将该弹投在任意方格内,炸弹爆炸后,以投弹方格为中心,半径R范围内的所有方格里的怪兽都会被消灭。何老板想知道,把这枚炸弹丢在哪个方格,可以消灭最多的怪兽,请你帮他算算。
    注:若投弹处坐标为(x,y)也就是说,与(x,y)距离小于等于R的方格都会被杀伤。
    坐标为(x1,y1)和坐标为(x2,y2)的方格间的距离

    输入格式

    第一行,三个空格间隔的整数n、m和R,n和m分别表示矩阵的行数和列数,R表示该炸弹的杀伤半径
    接下来一个n*m的整数矩阵,数字间以空格做间隔,表示游戏地图

    输出格式

    一行,一个整数,表示消灭的最多怪兽数量。

    样例输入

    6 6 2
    2 0 1 2 1 2
    3 3 1 5 1 1
    1 1 2 1 2 1
    1 2 1 0 1 1
    4 0 2 1 1 0
    1 0 2 0 1 1

    样例输出

    22

    提示

    数据范围
    1<=n,m<=100
    1<=R<=10
    0<=每个格子的怪兽数量<=1000
    样例说明
    将炸弹投放在坐标为(3,3)的格子,爆炸波及范围如蓝色虚线所示,红色方格表示被杀伤的区域。
    红色方格的数字之和为22