Logo Daimayuan Online Judge

Home

时间限制:5 s 空间限制:1024 MB

#614. “Z”型矩阵

附加文件 统计

对于一个只包含 .z 的矩阵,当以下条件满足时:

  1. 该矩阵的行数列数相等。

  2. 该矩阵的第一行与最后一行的字符全是 z

  3. 该矩阵从右上角到左下角的对角线上的字符全是 z

我们称其为 Z 矩阵。

现在给定一个 $n \times m$ 的矩阵,请你计算它有多少个子矩阵是 Z 矩阵。

输入格式

第一行两个整数 $n$ , $m$ 分别表示矩阵的行数和列数 $(1 \leq n , m \leq 3 \times 10^3 )$。

接下来 $n$ 行, 每行包含 $m$ 个字符, 表示该矩阵。

输出格式

输出一行一个整数表示 Z 矩阵的数量。

样例输入

4 4
zzzz
z.z.
.zz.
zzzz

样例输出

14