https://ac.nowcoder.com/acm/problem/53676
题意:给定一个由01字符串矩阵,求包含1的k*k矩阵个数。

分析:地图大小为10001000,枚举kk矩阵即可,若矩阵数字和不为0,则ans++
求区间和我们首先想到前缀和,可以O(1)查询区间和,感觉和昨天的题差不多,把字符数组转化为整形数组,前缀和预处理下然后查询即可,只不过这题要用到二维数组的前缀和。sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+b[i][j] 具体实现自己画个矩形图模拟下就可以理解了,本质上和一维数组差不多。

代码:

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<queue>
using namespace std;
typedef long long ll;
int n,m,k,i,j,ans;
char a[1002][1002];
int b[1002][1002];
int sum[1002][1002];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(i=0;i<n;i++){
        scanf("%s",a[i]);
        for(j=0;j<m;j++){
            if(a[i][j]=='1'){
                b[i+1][j+1]=1;//将01字符串储存到整形数组中
            }
        }
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+b[i][j];//前缀和处理
        }
    }
    for(i=1;i<=n-k+1;i++){
        for(j=1;j<=m-k+1;j++){
            ll tmp=sum[i+k-1][j+k-1]-sum[i-1][j+k-1]-sum[i+k-1][j-1]+sum[i-1][j-1];//前缀和求k!区间和
            if(tmp!=0){//区间和不为0,即有建筑
                ans++;
            }
        }
    }
    printf("%d",ans);
}