P7715 "EZEC-10" Shape

It is defined that $(x,y)$ denotes the cell in row $x$ and column $y$.

Person A has an $n \times m$ grid. Some cells are white, and the remaining cells are black. Person A chooses four integers $x_1, x_2, y_1, y_2$ satisfying the following conditions: 1. $1 \le x_1 < x_2 \le n$ and $1 \le y_1 < y_2 \le m$. 2. $x_1 + x_2$ is even. If all cells on the following three segments are white: $(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)$, then the shape formed by these three segments is called an H-shape. Person A wants to know how many different H-shapes exist in the grid. **Two H-shapes are the same if and only if their $x_1, x_2, y_1, y_2$ are all the same.**

The first line contains two integers $n, m$. The next $n$ lines each contain $m$ integers describing the grid, where $0$ means a white cell and $1$ means a black cell.

Output one integer, representing the number of different H-shapes.

**[Sample 1 Explanation]** The H-shape with $(x_1,x_2,y_1,y_2)=(1,3,3,4)$ is valid. **[Sample 2 Explanation]** The H-shapes with $(x_1,x_2,y_1,y_2)=(1,5,1,3)$ and $(2,4,1,3)$ are valid. **[Constraints]** **This problem uses bundled testdata.** - Subtask 1 (1 point): $n=2$. - Subtask 2 (9 points): $n, m \le 50$. - Subtask 3 (10 points): $n, m \le 100$, **time limit is $500ms$**. - Subtask 4 (30 points): $n, m \le 500$. - Subtask 5 (50 points): no special constraints. For $100\%$ of the data, $2 \le n, m \le 2 \times 10^3$. Translated by ChatGPT 5