#3125. 「COCI 2018.10」Strah

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

译自 COCI 2018/2019 Contest #1 T4「Strah

对于 Mirko 来说,他最害怕的事情就是找位置种草莓。Mirko 有 N \times M 块田地,有的位置适合种草莓而有的不适合,因为有杂草。一个合适矩形是指这个矩形中的每一块田地都是适合种草莓的。Mirko 对每一块田地的潜力值很感兴趣。一块田地的潜力值是有多少个合适矩形覆盖它。

请你帮助 Mirko 算出所有田地潜力值的和。

输入格式

第一行输入两个正整数 N, M

接下来 N 行,每行一个长为 M 的字符串,只由 .# 组成,. 表示这块田地适合种草莓,# 表示这块田地不适合。

输出格式

一行输出一个整数,表示所有田地的潜力值之和。

样例

样例输入 1

2 3
.#.
..#

样例输出 1

8

样例解释 1

每块土地的潜力值如下所示:

2 0 1
3 2 0

样例输入 2

3 3
...
...
...

样例输出 2

100

样例输入 3

3 4
..#.
#...
...#

样例输出 3

40

数据范围与提示

对于 20\% 的数据,保证 N, M \le 10

对于 50\% 的数据,保证 N, M \le 300

对于 100\% 的数据,保证 1\le N, M \le 2 \times 10^3