← 返回题目列表

AtCoder · bitflyer2018_qual_d

D. 邮票

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

配点 : 500 点

問題文

H 行 W 有一张写着 列方格的纸。 从这个方格的上方数第 i 行,从左方数 j 列的方格(1 \leq i \leq H, 1 \leq j \leq W)称为方格 (i, j) 记作。

这个方格的 N 行 M 有一个大小与这些方格的列数相同的印章。 这个印章的印影由 N 个的长度 M 的字符串 A_1, A_2, ..., A_N 将印章的左上角对准方格 (s, t) (1 \leq s \leq H - N + 1, 1 \leq t \leq W - M + 1)的左上角 对齐后盖章,印章覆盖的各个方格 (u, v) (s \leq u \leq s + N - 1, t \leq v \leq t + M - 1)的颜色会如下变化。

  • 文字列 A_i 的 j 第...个字符为 # 时,方格 (s + i - 1, t + j - 1) 的颜色会变为黑色。
  • 文字列 A_i 的 j 第...个字符为 . 时,方格 (s + i - 1, t + j - 1) 的颜色不会发生变化。

最初,所有方格的颜色都是白色。 1 \leq s \leq H - N + 1, 1 \leq t \leq W - M + 1 对于满足...的每个 s, t , 将印章的左上角与方格 (s, t) 的左上角对齐后盖章。

请计算颜色变为黑色的方格数量。

制約

  • 1 \leq H, W \leq 10^9
  • 1 \leq N, M \leq 1000
  • N \leq H
  • M \leq W
  • |A_i| = M (1 \leq i \leq N)
  • 各 i 对于,A_i 的每个字符是 # 和 我讨厌 . 中的某一个

入力

输入是按以下格式从标准输入给出的。

H W
N M
A_1
A_2
:
A_N

出力

请输出答案。


入力例 1

3 4
2 3
..#
##.

出力例 1

9

将印章的左上角对准格子后按下。 (1, 1), (1, 2), (2, 1), (2, 2) 的 4 将按照相应位置按下印章。 如果按照这个顺序依次按下印章,各个格子的颜色会如图所示发生变化。

在所有位置都按下印章后,颜色变为黑色的格子有 9 个。

abdf492090c7f44749c1243f34bae924.png

入力例 2

5 5
4 4
####
#..#
#..#
####

出力例 2

24

除正中央以外的格子都会变黑。


入力例 3

10 12
1 1
.

出力例 3

0

入力例 4

20 20
5 5
##.##
.##.#
..##.
...##
....#

出力例 4

390

入力例 5

1000000000 1000000000
5 4
.#..
....
..#.
.#..
....

出力例 5

999999996999999999