#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int INF = 1000000007;
int dc[4] = {'N', 'W', 'S', 'E'};
int nexty[4] = {-1, 0, 1, 0};
int nextx[4] = {0, -1, 0, 1};
bool inside(int R, int C, int y, int x) {
return 0 <= y && y < R && 0 <= x && x < C;
}
bool inmax(int &a, int b) {
if(b > a) {
a = b;
return true;
}
return false;
}
int ctod(char c) {
for(int i = 0; i < 4; i++) {
if(c == dc[i]) return i;
}
return -1;
}
int main() {
int M, R, C;
scanf("%d%d%d", &M, &R, &C);
char D[M * 2];
scanf("%s", D);
for(int i = 0; i < M; i++) D[M + i] = D[i];
int U[R][C];
for(int i = 0; i < R; i++) {
for(int j = 0; j < C; j++) {
scanf("%d", U[i] + j);
}
}
int cnt[1 << 4];
int thr[1 << 4];
fill(cnt, cnt + (1 << 4), 0);
fill(thr, thr + (1 << 4), 0);
for(int i = 0; i < M * 2; i++) {
int d = ctod(D[i]);
for(int j = 0; j < (1 << 4); j++) {
if((j >> d) & 1) {
cnt[j]++;
} else {
inmax(thr[j], cnt[j]);
cnt[j] = 0;
}
}
}
for(int j = 0; j < (1 << 4); j++) {
if(cnt[j] == M * 2) {
thr[j] = INF;
}
}
pair<int, int> cor[R * C];
for(int i = 0; i < R; i++) {
for(int j = 0; j < C; j++) {
cor[C * i + j] = make_pair(i, j);
}
}
random_shuffle(cor, cor + R * C);
int min = INF;
int cnt2 = 0;
int cnt3 = 0;
bool fin[R][C], stt[R][C];
fill(fin[0], fin[R], false);
fill(stt[0], stt[R], false);
for(int i = 0; i < R * C; i++) {
stt[cor[i].first][cor[i].second] = true;
if(U[cor[i].first][cor[i].second] == 0) continue;
queue<pair<int, int> > Q;
queue<pair<int, int> > Q1;
int cnt1 = 1;
fin[cor[i].first][cor[i].second] = true;
Q1.push(cor[i]);
for(int k = 0; k < 4; k++) {
int ny = cor[i].first + nexty[k];
int nx = cor[i].second + nextx[k];
if(inside(R, C, ny, nx)) Q.push(make_pair(ny, nx));
}
for(; !Q.empty();) {
cnt3++;
pair<int, int> rem = Q.front();
Q.pop();
if(U[rem.first][rem.second] == 0 || fin[rem.first][rem.second]) continue;
int ds = 0;
for(int k = 0; k < 4; k++) {
if(inside(R, C, rem.first + nexty[k], rem.second + nextx[k]) && fin[rem.first + nexty[k]][rem.second + nextx[k]]) {
ds += (1 << k);
}
}
if(U[rem.first][rem.second] <= thr[ds]) {
if(stt[rem.first][rem.second]) {
cnt1 = -1;
break;
}
cnt1++;
fin[rem.first][rem.second] = true;
Q1.push(make_pair(rem.first, rem.second));
for(int k = 0; k < 4; k++) {
int ny = rem.first + nexty[k];
int nx = rem.second + nextx[k];
if(inside(R, C, ny, nx)) Q.push(make_pair(ny, nx));
}
}
}
for(; !Q1.empty();) {
fin[Q1.front().first][Q1.front().second] = false;
Q1.pop();
}
if(cnt1 == -1) continue;
if(cnt1 < min) {
min = cnt1;
cnt2 = 0;
}
if(cnt1 == min) cnt2 += cnt1;
}
printf("%d\n%d\n", min, cnt2);
return 0;
}
Compilation message
virus.cpp: In function 'int main()':
virus.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &M, &R, &C);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
virus.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", D);
~~~~~^~~~~~~~~
virus.cpp:41:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", U[i] + j);
~~~~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
367 ms |
9080 KB |
Output is correct |
3 |
Correct |
710 ms |
9080 KB |
Output is correct |
4 |
Correct |
714 ms |
9116 KB |
Output is correct |
5 |
Correct |
388 ms |
9208 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
760 ms |
9332 KB |
Output is correct |
8 |
Correct |
149 ms |
3960 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
7 ms |
504 KB |
Output is correct |
3 |
Correct |
10 ms |
504 KB |
Output is correct |
4 |
Correct |
8 ms |
504 KB |
Output is correct |
5 |
Correct |
9 ms |
504 KB |
Output is correct |
6 |
Correct |
12 ms |
504 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
10 ms |
504 KB |
Output is correct |
9 |
Correct |
4 ms |
376 KB |
Output is correct |
10 |
Correct |
8 ms |
504 KB |
Output is correct |
11 |
Correct |
4 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
376 KB |
Output is correct |
13 |
Correct |
11 ms |
632 KB |
Output is correct |
14 |
Correct |
15 ms |
504 KB |
Output is correct |
15 |
Correct |
11 ms |
504 KB |
Output is correct |
16 |
Correct |
12 ms |
504 KB |
Output is correct |
17 |
Correct |
7 ms |
376 KB |
Output is correct |
18 |
Correct |
4 ms |
376 KB |
Output is correct |
19 |
Correct |
10 ms |
504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
367 ms |
9080 KB |
Output is correct |
3 |
Correct |
710 ms |
9080 KB |
Output is correct |
4 |
Correct |
714 ms |
9116 KB |
Output is correct |
5 |
Correct |
388 ms |
9208 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
760 ms |
9332 KB |
Output is correct |
8 |
Correct |
149 ms |
3960 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
7 ms |
504 KB |
Output is correct |
11 |
Correct |
10 ms |
504 KB |
Output is correct |
12 |
Correct |
8 ms |
504 KB |
Output is correct |
13 |
Correct |
9 ms |
504 KB |
Output is correct |
14 |
Correct |
12 ms |
504 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
10 ms |
504 KB |
Output is correct |
17 |
Correct |
4 ms |
376 KB |
Output is correct |
18 |
Correct |
8 ms |
504 KB |
Output is correct |
19 |
Correct |
4 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
376 KB |
Output is correct |
21 |
Correct |
11 ms |
632 KB |
Output is correct |
22 |
Correct |
15 ms |
504 KB |
Output is correct |
23 |
Correct |
11 ms |
504 KB |
Output is correct |
24 |
Correct |
12 ms |
504 KB |
Output is correct |
25 |
Correct |
7 ms |
376 KB |
Output is correct |
26 |
Correct |
4 ms |
376 KB |
Output is correct |
27 |
Correct |
10 ms |
504 KB |
Output is correct |
28 |
Execution timed out |
1079 ms |
14488 KB |
Time limit exceeded |
29 |
Halted |
0 ms |
0 KB |
- |