CF628E.Zbazi in Zeydabad

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

A tourist wants to visit country Zeydabad for Zbazi (a local game in Zeydabad).

The country Zeydabad is a rectangular table consisting of nn rows and mm columns. Each cell on the country is either 'z' or '.'.

The tourist knows this country is named Zeydabad because there are lots of ''Z-pattern"s in the country. A ''Z-pattern" is a square which anti-diagonal is completely filled with 'z' and its upper and lower rows are also completely filled with 'z'. All other cells of a square can be arbitrary.

Note that a ''Z-pattern" can consist of only one cell (see the examples).

So he wants to count the number of ''Z-pattern"s in the country (a necessary skill for Zbazi).

Now your task is to help tourist with counting number of ''Z-pattern"s.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use gets/scanf/printf instead of getline/cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

输入格式

The first line contains two integers n,mn,m ( 1<=n,m<=30001<=n,m<=3000 ) — the number of rows and columns respectively.

Each of the next nn lines contains mm characters 'z' or '.' — the description of Zeydabad.

输出格式

Print the only integer aa — the number of ''Z-pattern"s in Zeydabad.

输入输出样例

  • 输入#1

    4 4
    zzzz
    zzz.
    .z..
    zzzz
    

    输出#1

    16
    
  • 输入#2

    1 4
    z.z.
    

    输出#2

    2
    
  • 输入#3

    2 2
    zz
    zz
    

    输出#3

    5
    
首页