CF847I Noise Level

贝尔兰首都的城市版图为一个 $n \times m$ 的矩形，共有 $n$ 行 $m$ 列居民区。所有的居民区分为三种类型： - 普通区（用字符 '.' 表示） —— 这种居民区不产生噪音，但不会阻挡噪音的传播； - 噪音源（用大写拉丁字母 'A' 到 'Z' 表示） —— 这种居民区是噪音源，同时也不阻挡噪音的传播； - 高楼密集区（用字符 '*' 表示） —— 这种居民区隔音良好，噪音无法渗入，并且会阻挡噪音的传播。 标有字母 'A' 的居民区会产生 $q$ 单位的噪音。标有字母 'B' 的居民区会产生 $2q$ 单位的噪音。依此类推，标有字母 'Z' 的居民区会产生 $26q$ 单位的噪音。城市中每种字母的居民区数量不限。 噪音从噪音源传播时，每向相邻（四个方向之一）居民区传播一次时，噪音强度减半（如果为奇数则向下取整）。噪音传播只沿着可达的通路进行，例如距离噪音源 $2$ 的某个居民区，其受到的噪音会是源噪音除以 $4$，依次类推。每一处居民区受到的噪音仅与其到噪音源的最短路径长度有关。高楼密集区为障碍物，噪音无法穿透。 下图（见题面）给出了 $q=100$ 时的一个例子，表格右侧格子的数值表示对应居民区受到的总噪音，括号内的每一项分别为某个噪音源到达该居民区的贡献。某一居民区的噪音总量为所有噪音源对其的贡献之和。为评估贝尔兰首都居民的生活质量，需要计算噪音总量超过允许上限 $p$ 的居民区数量。

第一行包含四个整数 $n$、$m$、$q$ 和 $p$，分别表示贝尔兰首都的行数、列数，每个 'A' 区域产生的噪音值 $q$，以及允许的最大噪音值 $p$（$1 \leq n,m \leq 250$，$1 \leq q,p \leq 10^{6}$）。 接下来的 $n$ 行，每行包含 $m$ 个字符，描述首都的各个居民区。描述方式见题面。可能不会出现所有类型。

输出一行，表示噪音总量超过允许值 $p$ 的居民区数量。

第一个样例的插图见题面正文。 由 ChatGPT 5 翻译