Codeforces 847 I

Posted on | | 阅读数 次
Words count in article: 1.2k | Reading time ≈ 6

I. Noise Level

开启传送门

题目描述

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\cdot q$ units of noise. And so on, up to a quarter labeled with letter ‘Z’, which produces $26\cdot 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

The first line contains four integers $n, m, q$ and $p$ ($1 ≤ n, m ≤ 250, 1 ≤ q, p ≤ 10^6$) — 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

Print the number of quarters, in which the noise level exceeds the allowed level $p$.

Examples

input1

3 3 100 140

…

A*.

.B.

output1

3

input2

3 3 2 8

B*.

BB*

BBB

output2

4

input3

3 4 5 4

..*B

..**

D…

output3

7

Note

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

题意

zuhiul家里有很多妹子，但是有一天，妹子们对他都很不满，所以妹子们都在呼叫他，如你所见，妹子在一些点中，并且每个妹子的音量都是他的倍数，其中 A 表示一倍，B表示两倍，最厉害的妹子甚至可以喊出他 26 倍音量（也即 Z ），但是好处是，每个妹子的音量都会随着哈密顿距离指数级减半。zuhiul的耳朵有个承受上线，如果太多杂音，他会受不了。现在问，有多少个位置的音量是zuhiul可接受的。注意，他不能和妹子一个位置。也不能在*上。

分析

一个显然的做法是，我们可以直接把每个有音量的地方传播下去，就可以得到一个比较完美的图。然后把音量叠加后枚举每个位置，判断当前音量是否超过阈值即可。

可以发现的是，因为每次音量都是倍减的，所以可以得到，最多倍减log次，所以对于一个音量来说，最大的传播范围是O($log(p_{max})log(p_{max})$) ，所以复杂度是O($nmlog(p_{max})log(p_{max})$)

代码

给大佬递上我奇丑无比的代码　(/ω＼)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <iostream>
using namespace std;

const int maxm = 300;
int n, m;
long long a, b;
char mat[maxm][maxm];
long long ans[maxm][maxm];

struct p {
	int x,y,val;
};
int dirx[] = {0,0,1,-1};
int diry[] = {1,-1,0,0};
bool vis[maxm][maxm];

vector<p> vis_buf;

void gao(int a,int b, int val) {
	queue<p> q;
	vis_buf.resize(0);
	q.push(p{a,b,val});
	vis_buf.push_back(p{a,b,val});
	vis[a][b] = true;
	ans[a][b] += val;
	while(!q.empty()) {
		p buf = q.front();
		q.pop();
		if(buf.val==0) continue;
		for(int dir = 0;dir<4;dir++) {
			int x = buf.x + dirx[dir];
			int y = buf.y + diry[dir];
			if(x<0||y<0||x>=n||y>=m) continue;
			if(mat[x][y]=='*') continue;
			if(vis[x][y]) continue;
			vis[x][y] = true;
			vis_buf.push_back(p{x,y,0});
			ans[x][y] += buf.val>>1;
			q.push(p{x,y,buf.val>>1});
		}
	}
	for(auto i:vis_buf) {
		vis[i.x][i.y] = false;
	}
}



int main() {
		scanf("%d%d%lld%lld", &n, &m, &a, &b);
		for (int i = 0; i < n; i++) scanf("%s", mat[i]);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
						if (mat[i][j] == '*') continue;
						int val = mat[i][j] == '.' ? 0 : (mat[i][j] - 'A' + 1) * a;
						if(val==0) continue;
						gao(i,j,val);
				}
		}
	int rans = 0;
	for(int i = 0;i<n;i++) for(int j = 0;j<m;j++) if(ans[i][j]>b) rans++;
	printf("%d\n", rans);
	return 0;
}