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); }