← 返回题目列表

Codeforces · 435/D

D. 特殊网格

中文机器翻译题面 查看原题

给定一个 n × m 的网格,其中一些节点是黑色的,其他节点是白色的。而且,它不是一个普通的网格——网格的每个单位方块都画有对角线。

下图是一个大小为 3 × 5 的网格的示例。该网格的 4 个节点是黑色的,其他 11 个节点是白色的。

您的任务是计算给定网格上此类三角形的数量:

- 角点与白色节点匹配,面积为正;
- 所有边都沿着网格线(水平、垂直或对角线);
- 没有边包含黑色节点。

输入

第一行包含两个整数 n 和 m (2 ≤ n, m ≤ 400)。以下 n 行中的每一行都包含 m 个字符(零和一)——网格的描述。如果第 i 行中的第 j 个字符等于 0,则第 i 水平行和第 j 垂直行上的节点被涂成白色。否则,该节点将被涂成黑色。

水平线从上到下从 1 开始编号,垂直线从左到右从 1 开始编号。

输出

打印一个整数 — 所需三角形的数量。

示例

输入 #1

3 5
10000
10010
00001

输出 #1

20

输入 #2

2 2
00
00

输出 #2

4

输入 #3

2 2
11
11

输出 #3

0

注意

下图显示了红色和蓝色三角形。它们是第一个示例中所需三角形的示例。无效三角形之一被涂成绿色。这是无效的,因为并非所有边都沿着网格线。