← 返回题目列表

Codeforces · 847/I

I. 噪音水平

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

Berland 的首都呈矩形,大小为 n × m 四分之一。所有宿舍分为三种类型:

- 常规(标有字符“.”)——此类区域不会产生噪音,但不会成为噪音传播的障碍;
- 噪声源(用从“A”到“Z”的大写拉丁字母标记)——此类区域是噪声源,并且不会阻碍噪声传播;
- 建筑密集(标有字符“*”)——此类宿舍是隔音的,噪音不会渗透到其中,而且它们本身就是噪音传播的障碍。

标有字母“A”的四分之一产生 q 单位的噪声。标有字母“B”的四分之一产生 2·q 单位的噪声。依此类推,最多四分之一标有字母“Z”,它产生 26·q 单位的噪声。城市中可以有任意数量的用每个字母标记的街区。

当从噪声源传播时,当从四分之一移动到与其共享一侧的四分之一时,噪声级别会减半(当奇数要减半时,会向下舍入)。噪音沿着链条传播。例如,如果某个四分之一区距噪声源的距离为 2,则到达该四分之一区的噪声值将除以 4。因此,从源到该四分之一区的噪声级别仅由它们之间的最短路径长度决定。建筑密集的住宅区是障碍物,噪音无法渗透到其中。

右侧表格单元格中的值显示 q = 100 时各个季度的总噪声水平,每个总和中的第一项是来自季度“A”的噪声,第二项是来自季度“B”的噪声。

四分之一的噪声水平定义为所有源噪声的总和。为了评估贝尔兰首都居民的生活质量,需要找出噪音水平超过允许水平 p 的小区数量。

输入

第一行包含四个整数 n、m、q 和 p(1 ≤ n、m ≤ 250、1 ≤ q、p ≤ 106)——Berland 首都的大小、四分之一“A”产生的噪音单位数量以及允许的噪音水平。

以下 n 行中的每一行都包含 m 个字符 - 对首都地区的描述,采用上面语句中描述的格式。贝尔兰首都可能没有任何类型的宿舍。

输出

打印噪音水平超过允许水平的季度数 p。

示例

输入 #1

3 3 100 140
...
A*.
.B.

输出 #1

3

输入 #2

3 3 2 8
B*.
BB*
BBB

输出 #2

4

输入 #3

3 4 5 4
..*B
..**
D...

输出 #3

7

注意

第一个示例的说明位于语句的主要部分。