「EZEC-10」Shape
题目背景
规定 $(x,y)$ 表示第 $x$ 行第 $y$ 列的格子。
题目描述
小 A 有一个 $n\times m$ 的网格,一些为白色格子,剩余为黑色格子。
小 A 选择四个整数 $x_1,x_2,y_1,y_2$,满足如下条件:
1. $1\le x_1<x_2\le n$ 且 $1\le y_1<y_2\le m$。
2. $x_1+x_2$ 为偶数。
若 $(x_1,y_1)\to (x_2,y_1),(x_1,y_2)\to (x_2,y_2),(\frac{x_1+x_2}{2},y_1)\to (\frac{x_1+x_2}{2},y_2)$ 这三段中的格子均为白色,则称这三段构成的图形为 H 形。
小 A 想知道,这个网格中存在多少不同的 H 形。
**两个 H 形相同,当且仅当两个 H 形的 $x_1,x_2,y_1,y_2$ 均相同。**
输入输出格式
输入格式
第一行两个整数 $n,m$。
后 $n$ 行每行 $m$ 个整数表示网格,其中 $0$ 代表白色,$1$ 代表黑色。
输出格式
一个整数,表示不同 H 形的数量。
输入输出样例
输入样例 #1
3 4
1 0 0 0
1 1 0 0
1 0 0 0
输出样例 #1
1
输入样例 #2
5 3
0 1 0
0 1 0
0 0 0
0 1 0
0 1 0
输出样例 #2
2
说明
**【样例 1 解释】**
$(x_1,x_2,y_1,y_2)=(1,3,3,4)$ 的 H 形符合。
**【样例 2 解释】**
$(x_1,x_2,y_1,y_2)=(1,5,1,3),(2,4,1,3)$ 的 H 形符合。
**【数据规模与约定】**
**本题采用捆绑测试。**
- Subtask 1(1 point):$n=2$。
- Subtask 2(9 points):$ n,m\le 50$。
- Subtask 3(10 points):$ n,m\le 100$,**时限为 $500ms$**。
- Subtask 4(30 points):$ n,m\le 500$。
- Subtask 5(50 points):无特殊限制。
对于 $100\%$ 的数据,$2\le n,m\le 2\times 10^3$。