#1253 · ZSHAPE

Given a grid of size n \times m, where each cell in the grid contains either 0 or 1. Write a program to count the number of Z-shaped figures consisting entirely of 1's that appear in the grid.

An Z-shaped figure consists of:

Two horizontal lines consisting entirely of 1's, containing at least two 1's and of the same length. These two lines are located in two different rows in the grid.

A diagonal line consisting entirely of 1's connecting the rightmost cell of the upper horizontal line to the leftmost cell of the lower horizontal line. This diagonal line forms a 45-degree angle with the two horizontal lines.

The following are some valid Z-shaped figures:

The following are some invalid Z-shaped figures:

• The first line contains two positive integers n and m, which are the number of rows and columns in the grid.
• The next n lines each contain m characters, which are either 0 or 1, representing the grid.

A single line containing a single integer, which is the number of Z-shaped figures in the given grid.

Note that this value may be larger than the limit of the int type in C++ or longint type in Pascal.