#6571. 方格稿纸

方格稿纸

问题描述:

小y 终于在小学学会了一些字、词、句子,会写一点作文了。

某一天,小 y买了一张方格稿纸来写作文,稿纸是n nmm 列的,形状如下所示(图中n=m=5 n=m=5): image1

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

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

  1. 黑白格子的数量差不能超过 1;
  2. k2k\ge 2

上图染色后的方格稿纸共有 9 个魔幻方阵(66 2×2 2×2 的魔幻方阵,33 3×33×3 的魔幻方阵)。现在,请你帮助小 y 编程计算被染色的稿纸里面有多少个魔幻方阵。

输入格式:

第一行有2 2 个正整数n n m m(之间以一个空格分隔),表示n nm m 列的稿纸。接下来n n 行,每行有m m 0 0 1 1的整数(之间以一个空格分隔),代表这一行中每一个格子的颜色。如果这个数是11 则为黑色,是0 0 则为白色。

输出格式:

输出一行一个整数,表示稿纸中魔幻方阵的个数。

样例:

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% 50\%的数据满足:1n,m101≤n,m≤10

对于75% 75\%的数据满足:1n,m1801≤n,m≤180

对于100% 100\%的数据满足:1n,m3001≤n,m≤300