问题 1627. -- 方格稿纸

1627: 方格稿纸

时间限制: 1 Sec  内存限制: 128 MB
提交: 42  解决: 19
[提交][状态][讨论版]

题目描述

小猪在小学中认识了很多的字,终于会写一点作文了。某天小猪买了一张方格稿纸来写作文,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。

来源

[提交][状态]