农田个数

农田个数"/>

农田个数

农田个数

题目描述
你的老家在农村。过年时，你回老家去拜年。你家有一片N×MN×M农田，将其看成一个N×MN×M的方格矩阵，有些方格是一片水域。你的农村伯伯听说你是学计算机的，给你出了一道题： 他问你：这片农田总共包含了多少个不存在水域的正方形农田。

两个正方形农田不同必须至少包含下面的两个条件中的一条：

1.边长不相等

2.左上角的方格不是同一方格

输入格式

输入数据第一行为两个由空格分开的正整数N、M（1<=m< n <=1000）

第2行到第N+1行每行有M个数字（0或1），描述了这一片农田。0表示这个方格为水域，否则为农田（注意：数字之间没有空格，而且每行不会出现空格）

输出格式

满足条件的正方形农田个数。

样例数据
input

3 3
110
110
000

output

5

样例解释

边长为1的正方形农田有4块 边长为2的正方形农田有1块,合起来就是5块

`数据规模与约定
时间限制：1s1s
空间限制：256MB256MB

。其实我现在主要是来倾诉写完这道题的心酸的。