← 返回题目列表

Codeforces · 729/B

B. 聚光灯

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

剧院舞台是一个大小为 n × m 的矩形区域。导演给了你演员们要遵循的舞台计划。对于每个单元,计划中都会说明该单元中是否有演员。

您要将聚光灯放置在舞台上某个合适的位置。聚光灯将向四个方向之一投射光线(如果您从上方观察舞台)——左、右、上或下。因此,聚光灯的位置是它放置的单元格和它照射的方向。

如果满足两个条件,则该位置是良好的:

- 聚光灯所在的单元格中没有演员;
- 聚光灯投射方向至少有一名演员。

计算放置聚光灯的好位置的数量。如果位置单元或投影方向不同,则认为聚光灯的两个位置不同。

输入

第一行包含两个正整数 n 和 m (1 ≤ n, m ≤ 1000) — 计划中的行数和列数。

接下来的 n 行包含 m 个整数,每个整数 0 或 1 — 计划的描述。整数 1 表示相应单元格中将有一个参与者,而 0 表示该单元格将保持为空。保证计划中至少有一名演员。

输出

打印一个整数——放置聚光灯的好位置的数量。

示例

输入 #1

2 4
0 1 0 0
1 0 1 0

输出 #1

9

输入 #2

4 4
0 0 0 0
1 0 0 1
0 1 1 0
0 1 0 0

输出 #2

20

注意

在第一个示例中,以下位置比较合适:

1. (1, 1) 单元格和右方向;
2. (1, 1) 单元格向下方向;
3. (1, 3) 单元格向左方向;
4. (1, 3) 单元格向下方向;
5. (1, 4) 单元格向左方向;
6. (2, 2) 单元格向左方向;
7. (2, 2) 单元格向上方向;
8. (2, 2) 和右方向;
9. (2, 4) 单元格和向左方向。

因此,本例中有 9 个好的位置。