题面

小 y 终于在小学学会了一些字、词、句子， 会写一点作文了。某一天，小 y 买 了一张方格稿纸来写作文， 稿纸是 n 行 m 列的，形状如下所示（图中 n=m=5）：

某天小 y 的邻居小 x 来小 y 家玩， 无聊地用黑墨水笔把小 y 新买的方格稿纸 涂黑了很多格子。每个格子不是完全黑色就是完全白色，如下图所示。

小 y 不能责怪小 x。作文写不成了，他也觉得很无聊，就开始数里面有多少 “魔 幻方阵”。如果稿纸中一个 k×k 的正方形区域满足以下两个条件，那么它就是魔幻 方阵：

（1） 黑白格子的数量差不能超过 1； （2） k 不能小于 2。 上图染色后的方格稿纸共有 9 个魔幻方阵（6 个 2×2 的魔幻方阵， 3 个 3×3 的魔幻方阵）。

现在，请你帮助小 y 编程计算被染色的稿纸里面有多少个魔幻方阵。

对于 50%的数据满足： 1≤n≤10， 1≤m≤10； 对于 75%的数据满足： 1≤n≤180， 1≤m≤180； 对于 100%的数据满足： 1≤n≤300， 1≤m≤300。

分析

n3,二维前缀和随便乱搞。

代码

#include<bits/stdc++.h>using namespace std;#define N 303int w,b,n,m,ans;int a[N][N],white[N][N],black[N][N];inline void read(int &x){x=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}}int main(){read(n),read(m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){read(a[i][j]);white[i][j]=white[i-1][j]+white[i][j-1]-white[i-1][j-1]+(a[i][j]?0:1);black[i][j]=black[i-1][j]+black[i][j-1]-black[i-1][j-1]+(a[i][j]?1:0);} for(int k=2;k<=min(n,m);k++)for(int i=k;i<=n;i++)for(int j=k;j<=m;j++){w=white[i][j]-white[i-k][j]-white[i][j-k]+white[i-k][j-k];b=black[i][j]-black[i-k][j]-black[i][j-k]+black[i-k][j-k];if(abs(w-b)<=1)ans++;} printf("%d\n",ans);return 0;}