【每日一题】5月18日「土」秘法地震

题目大意: 帕秋莉掌握了一种土属性魔法

这种魔法可以在一片k×k大小的一个正方形区域内产生地震

但是如果某片即将产生地震的区域内有建筑物，帕秋莉会停止施法

整个地图大小为n×m，其中一些地方有建筑

请问有多少种可能的情况，使得帕秋莉会停止施法.

分析：枚举 子矩阵，判断矩阵中是否有1.
判断方法直接求子矩阵的元素和是否为0.
----------求子矩阵元素和常规技巧表示从 到 所组成的矩阵元素的和。
计算每 --(画图理解

如果要计算矩阵元素和
计算公式为 .------(同上,画图理解

#include<bits/stdc++.h>
using namespace std;

int mp[1005][1005],dp[1005][1005];

int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    for( int i=1;i<=n;i++ )
    {
        for( int j=1;j<=m;j++ )
        {
            scanf("%1d",&mp[i][j]);
            dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+mp[i][j];
        }
    }
    int ans=0;

    for( int i=k;i<=n;i++ )
    {
        for( int j=k;j<=m;j++ )
        {
            int num=dp[i][j]-(dp[i][j-k]+dp[i-k][j])+dp[i-k][j-k];
            if( num ) ans++;
        }
    }
    cout<<ans<<endl;
}