5624: 特殊网格
内存限制：256 MB
时间限制：2 S
题面：传统
评测方式：文本比较
上传者：
提交：4
通过：4
题目描述
You are given an n×m grid, some of its nodes are black, the others are white. Moreover, it's not an ordinary grid − each unit square of the grid has painted diagonals.
The figure below is an example of such grid of size 3×5. Four nodes of this grid are black, the other 11 nodes are white.
Your task is to count the number of such triangles on the given grid that:
The figure below is an example of such grid of size 3×5. Four nodes of this grid are black, the other 11 nodes are white.
Your task is to count the number of such triangles on the given grid that: - the corners match the white nodes, and the area is positive;
- all sides go along the grid lines (horizontal, vertical or diagonal);
- no side contains black nodes.
Input
The first line contains two integers n and m (2≤n,m≤400). Each of the following n lines contain m characters (zeros and ones) − the descThe horizontal lines are numbered starting from one from top to bottom, the vertical lines are numbered starting from one from left to right.
Output
Print a single integer − the number of required triangles.
给你一个n×m的网格，它的一些节点是黑色的，其他的是白色的。此外，它不是一个普通的网格——网格的每个单位正方形都画有对角线。
下图是尺寸为3×5的网格示例。此网格的四个节点为黑色，其他11个节点为白色。
您的任务是计算给定网格上这样的三角形的数量：
角与白色节点匹配，面积为正；
所有边都沿着网格线（水平、垂直或对角线）；
没有边包含黑色节点。
Examples
Input
3 5 10000 10010 00001
Output
20
Input
2 2 00 00
Output
4
Input
2 2 11 11
Output
0
Note
The figure below shows red and blue triangles. They are the examples of the required triangles in the first sample. One of the invalid triangles is painted green. It is invalid because not all sides go along the grid lines. 
输入样例 复制
输出样例 复制