| |
 54088[5,6]
|
2.五六年级学案：
1.方格稿纸
【题目描述】
小猪在小学中认识了很多的字，终于会写一点作文了。某天小猪买了一张方格稿纸来写作文，n行m列，形状如下所示：
::点击图片在新窗口中打开::
方格稿纸示意图
上图中n=m=5。
某天小猪的邻居小小猪来小猪家玩，用黑墨水笔把小猪新买的方格稿纸涂黑了很多格子。每个格子不是完全黑色就是完全白色，如下图所示。
小猪不能责怪小小猪。作文写不成了，他觉得很无聊，就开始数里面有多少魔幻方阵。
如果稿纸中一个k×k的正方形区域满足以下两个条件，那么它就是魔幻方阵：
1．黑白格子的数量差不能超过1；
2．k不能小于2。
::点击图片在新窗口中打开::
上图染色后的方格稿纸共有9个魔幻方阵（6个2×2的魔幻方阵，3个3×3的魔幻方阵），现在请你帮小猪求出他被染色的稿纸里面有多少个魔幻方阵。
【输入】
输入文件paint.in中的第一行有二个正整数n和m（互相之间以一个空格分隔），表示稿纸共有n行m列。
接下来n行，每行有m个0或1的整数（互相之间以一个空格分隔），代表每个格子的颜色。如果这个数是1则为黑色，是0则为白色。
【输出】
输出文件paint.out中仅有一行，该行只有一个整数，表示稿纸中魔幻方阵的个数。
【样例输入】
5 5
1 0 1 1 1
1 0 1 0 1
1 1 0 1 1
1 0 0 1 1
1 1 1 1 1
【样例输出】
9
【数据规模】
50%的数据，1≤n≤10，1≤m≤10；
75%的数据，1≤n≤180，1≤m≤180；
100%的数据，1≤n≤300，1≤m≤300。
参考程序：
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("p1078.in","r",stdin);
freopen("p1078.out","w",stdout);
int n,m,i,j,k,t,p,s=0,d;
short a[300][300]={0},b[300][300]={0};
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){scanf("%d",&a[i][j]);
b[i][j]=b[i][j-1]+b[i-1][j]-b[i-1][j-1]+a[i][j]; // b[i][j]存储从数组左上角（1,1）到(i,j)为右下角形成的矩形内1的个数
}
t= n>m?m:n;
for(k=2;k<=t;k++){ //枚举边长为k的正方形
for(i=k;i<=n;i++)
for(j=k;j<=m;j++){ //枚举以(i,j)为右下角，边长为k的正方形
p=b[i][j]-b[i-k][j]-b[i][j-k]+b[i-k][j-k] ;
d=k*k-p-p;
d= d>0?d:d*-1 ;
if(d<=1)s++;
}
}
printf("%d",s);
fclose(stdin);
fclose(stdout);
return 0;
}
( ) |
|
