2392:方格稿纸

文件提交:无需freopen 内存限制:128 MB 时间限制:1.000 S
评测方式:普通裁判
金币值:1
命题人:
提交:1 解决:1

题目描述

【题目描述】 

小猪在小学中认识了多的字,终于会写一点作文了。某天小猪买了一张方格稿纸来写作文,nm列,形状如下所示:


上图中n=m=5。 

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



小猪不能责怪小小猪。作文写不成了,他觉得很无聊,就开始数里面有多少魔幻方阵。 

如果稿纸中一个k×k正方形区域满足以下两个条件,那么它就是魔幻方阵: 

1黑白格子的数量差不能超过1; 

2k不能小于2。 

上图染色后方格稿纸共有9个魔幻方阵62×2魔幻方阵33×3魔幻方阵,现在请你帮小猪求出他被染色的稿纸里面有多少魔幻方阵。 

【输入】

输入文件paint.in中的第一有二个正整数nm(互相之间以一个空格分隔),表示稿纸共有nm列。

接下来n每行m01整数(互相之间以一个空格分隔),代表每个格子的颜色。如果这个数是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 

【样例输出】 

【数据规模】 

50%的数据,1n101m10; 

75%的数据,1n1801m180; 

100%的数据,1n3001m300

来源/分类