← 返回题目列表

Codeforces · 628/E

E. 泽达巴德的 Zbazi

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

一名游客想要前往 Zeydabad 国家玩 Zbazi(Zeydabad 的当地游戏)。

Zeydabad 国家是一个由 n 行和 m 列组成的矩形表。该国家/地区的每个单元格要么是“z”,要么是“.”。

游客知道这个国家被命名为Zeydabad,因为这个国家有很多“Z”图案。“Z”图案是一个反对角线完全充满“z”的正方形,其上下两行也完全充满“z”。正方形的所有其他单元格可以是任意的。

请注意,“Z 型图案”只能包含一个单元格(请参阅示例)。

所以他想统计全国“Z型”的数量(Zbazi的必备技能)。

现在你的任务是帮助游客计算“Z 型图案”的数量。

由于输入/输出可能达到巨大的尺寸,建议使用快速输入/输出方法:例如,在 C++ 中更喜欢使用 gets/scanf/printf 而不是 getline/cin/cout,在 Java 中更喜欢使用 BufferedReader/PrintWriter 而不是 Scanner/System.out。

输入

第一行包含两个整数 n, m (1 ≤ n, m ≤ 3000) — 分别是行数和列数。

接下来的 n 行中的每一行都包含 m 个字符“z”或“.” — 泽达巴德的描述。

输出

打印唯一的整数a——Zeydabad中“Z-pattern”的数量。

示例

输入 #1

4 4
zzzz
zzz.
.z..
zzzz

输出 #1

16

输入 #2

1 4
z.z.

输出 #2

2

输入 #3

2 2
zz
zz

输出 #3

5