Noise Level
Contest: 2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest, qualification stage (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 1900
Tags: dfs and similar, implementation, math

The Berland's capital has the form of a rectangle with sizes n × m quarters. All quarters are divided into three types:

- regular (labeled with the character '.') — such quarters do not produce the noise but are not obstacles to the propagation of the noise;
- sources of noise (labeled with an uppercase Latin letter from 'A' to 'Z') — such quarters are noise sources and are not obstacles to the propagation of the noise;
- heavily built-up (labeled with the character '*') — such quarters are soundproofed, the noise does not penetrate into them and they themselves are obstacles to the propagation of noise.

A quarter labeled with letter 'A' produces q units of noise. A quarter labeled with letter 'B' produces 2·q units of noise. And so on, up to a quarter labeled with letter 'Z', which produces 26·q units of noise. There can be any number of quarters labeled with each letter in the city.

When propagating from the source of the noise, the noise level is halved when moving from one quarter to a quarter that shares a side with it (when an odd number is to be halved, it's rounded down). The noise spreads along the chain. For example, if some quarter is located at a distance 2 from the noise source, then the value of noise which will reach the quarter is divided by 4. So the noise level that comes from the source to the quarter is determined solely by the length of the shortest path between them. Heavily built-up quarters are obstacles, the noise does not penetrate into them.

The values in the cells of the table on the right show the total noise level in the respective quarters for q = 100, the first term in each sum is the noise from the quarter 'A', the second — the noise from the quarter 'B'.

The noise level in quarter is defined as the sum of the noise from all sources. To assess the quality of life of the population of the capital of Berland, it is required to find the number of quarters whose noise level exceeds the allowed level p.

Input format:
The first line contains four integers n, m, q and p (1 ≤ n, m ≤ 250, 1 ≤ q, p ≤ 106) — the sizes of Berland's capital, the number of noise units that a quarter 'A' produces, and the allowable noise level.

Each of the following n lines contains m characters — the description of the capital quarters, in the format that was described in the statement above. It is possible that in the Berland's capital there are no quarters of any type.

Output format:
Print the number of quarters, in which the noise level exceeds the allowed level p.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
The illustration to the first example is in the main part of the statement.

Example input:
3 3 100 140
...
A*.
.B.

Example output:
3

Example input:
3 3 2 8
B*.
BB*
BBB

Example output:
4

Editorial:
Данная задача на реализацию. В ней нужно было запускать обход в ширину из каждого шумного квартала. Будем хранить в двумерном массиве суммарный уровень шума в каждом в квартале. В обходе в ширину для каждого квартала нужно использовать массив used, где мы будем хранить — были ли мы в клетке для текущего обхода в ширину, чтобы не прибавить несколько раз шум от текущего квартала к одной и той же клетке. Также нужно помнить, что есть кварталы-препятствия для шума, в них шум проникать не может.
После этого нужно лишь посчитать количество клеток в массиве суммарного шума, для которых уровень шума выше допустимого, и вывести ответ.