牛客——「土」秘法地震

牛客每日一题—— 「土」秘法地震

题意：问有多少个大小为k*k的矩阵的元素之和至少为1

思路：

​ 因为矩阵的大小已经固定，我们可以直接枚举一下左上角的区间端点，这样就可以根据端点和矩阵大小得到右下角的端点。

​ 这时候如果再遍历区间的话，复杂度就是O（n^4），所以我们要想办法优化一下。

​ 枚举是必不可少的，这时候就可以把查询变成O（1）查询。

​ 这时候就要用到二维前缀和了！

​ 前缀和是可以通过预处理的方式使得最后的查询为O（1）查询，一维的前缀和就是维护一个一维数组然后逐项累加，其中s[i]表示从1到i的数组元素的和，查询的时候只需要输出s[r]-s[l-1]即可。

二维前缀和则是维护一个二维数组，s[i] [j]表示左上角端点为（1，1），右下角端点为（i，j）的矩形的元素之和

    s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];

所以（x1,y1）,(x2,y2)的子矩阵之和就是

s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]

可以画图理解一下~

综上所述：本题可以先预处理出二维前缀和表示子矩阵的和，再通过枚举左上角端点的情况来得到大小为k*k的子矩阵的和，如果这个和大于1的话，答案就+1。

另外，对于矩阵的输入有两种方法，一是通过字符串或字符数组输入，二是可以通过

 scanf("%1d",&g[i][j]);

输入，表示逐位输入。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1100;
int s[maxn][maxn];
int a[maxn][maxn];
int n,m,k;

int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%1d",&a[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    int res=0;
    for(int i=1;i+k-1<=n;i++)
        for(int j=1;j+k-1<=m;j++)
                if(s[i+k-1][j+k-1]-s[i-1][j+k-1]-s[i+k-1][j-1]+s[i-1][j-1]>0) res++;
    cout<<res<<endl;
    return 0;
}