做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2509. -- 蒜头君打地鼠

2509: 蒜头君打地鼠

时间限制: 2 Sec  内存限制: 256 MB
提交: 3  解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

蒜头君最近迷上了打地鼠,但他发现同时出现在面板上的地鼠太多,于是他想改进一下他的锤子,于是他拿出了一款 k×kk \times kk×k 大小的正方形锤子,但是遗憾的是,这个锤子只能斜着砸。如下图所示:

1- - * - - 
2- * * * - 
3* * x * * 
4- * * * - 
5- - * - - 

k=2k=2k=2 时,若蒜头君敲击黑点,黑点和图中所有蓝色点将一并被敲到。

k=3k=3k=3 时,锤子的图案如下所示:


kkk 取其他值时以此类推。

注意:蒜头君只能敲击面板上的格子,但锤子不一定要全部落在面板内。

现在给定一个 n×nn \times nn×n 的面板,每个格子可能有地鼠也可能没有地鼠,请编程计算用 k×kk \times kk×k 大小锤子敲击时最多能打中多少地鼠。

输入格式

第一行 222 个整数 n,kn,kn,k,表示面板大小和锤子大小。

接下来 nnn 行,每行 nnn 个整数,若为 111 代表该格子有地鼠,若为 000 代表该格子无地鼠。不会出现其他的数字。

输出格式

输出一个整数,代表最多能砸到的地鼠数。

数据规模

对于 505050% 的测试数据,满足 1n300,1k101 \le n \le 300,1 \le k \le 101n300,1k10

对于 808080% 的测试数据,满足 1n2000,1k101 \le n \le 2000,1 \le k \le101n2000,1k10

对于 100100100% 的测试数据,满足 1n2000,1k1001 \le n \le 2000,1 \le k \le 1001n2000,1k100

样例说明

敲击第 222 行的 000,可以敲到周围的 444 个地鼠。

样例输入

3 2
0 1 1
1 0 1
0 1 0

样例输出

4

标签

[上一题][提交][讨论版][状态][下一题]