menu 大连理工大学 DP·AC算法竞赛协会 ICPC集训队 Online Judge
account_circle 请登录
home
首页
 book
题目
 library_books
题单
 apps
分类
 play_circle_outline
状态
 layers
竞赛/作业
 equalizer
排名
assignment_ind
登录
 person_add
注册
1039: 「土」秘法地震
时间限制：1.000s
内存限制：128MB
提交 通过: 15 提交: 26 统计

题目描述

帕秋莉掌握了一种土属性魔法  这种魔法可以在一片k×k大小的一个正方形区域内产生地震
但是如果某片即将产生地震的区域内有建筑物，帕秋莉会停止施法
整个地图大小为n×m，其中一些地方有建筑
请问有多少种可能的情况，使得帕秋莉会停止施法

输入格式

第一行三个数n, m, k，意义见描述
接下来一个n×m的01矩阵表示这篇区域的情况，1表示这个地方有建筑

输出格式

输出一个数表示答案

样例输入 content_copy 

4 4 2
1000
0100
0000
0001

样例输出 content_copy 

5

提示/说明

对于100%的数据，n, m≤1000，k≤min(n, m)

分类

前缀和-二维
提交