UOJ Logo

NOI.AC

1S 512MB

#1569. 噪音

Statistics

题目描述

有一个$n\*m$大小的街区,其中每片区域都可以归为以下三种类型之一: 1:空旷的街道(用字符$\text{'.'}$表示):可以让声音传播 2:噪音源(用26个大写字母表示):会发出噪音,也可以让来自其他方向的声音传播通过 3:隔音墙(用字符$\text{'*'}$表示):会吸收经过的所有声音

其中噪音源用26个大写字母标记,不同字母会发出不同大小的噪音,例如$A$会产生$p$大小的噪音,而$B$会产生$2\*p$大小的噪音,以此类推,$Z$会产生$26 \* p$大小的噪音。

声音在传播的过程中,每经过一片区域,都会减半(如果大小为奇数则减半后向下取整)。同时,一个噪音源可能通过不同的路径传播声音到同一片区域,所以我们认为经过区域较少抵达的声音为当前噪音源在此处产生的噪音。

因为可能有多个噪音源,所以规定在任意一片区域的噪音分贝数,为所有噪音源的声音经过传播后抵达这片区域后大小的总和。

现在,政府希望治理噪音过大的区域,请问噪音分贝大于$q$的区域有几个

输入格式

第一行四个数$n,m,p,q$ 下面$n$行,每行$m$个字符表示当前区域的类型

输出格式

一个整数表示答案

样例数据

input

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

output

3

样例解释

50+25=7525+12=3712+25=37
100+50=15006+50=56
50+100=15025+200=22512+100=112

数据规模与约定

对于40%的数据,$n,m\le 10$ 对于另外20%的数据,$q=0$ 对于100%的数据,$n,m\le 250,p\le 10^{6},q\le 10^{9}$