#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);
fprintf(stderr, "%d\n", cnt3);
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]
34 | 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]
36 | scanf("%s", D);
| ~~~~~^~~~~~~~~
virus.cpp:41:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | scanf("%d", U[i] + j);
| ~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
173 ms |
9056 KB |
Output is correct |
3 |
Correct |
374 ms |
12624 KB |
Output is correct |
4 |
Correct |
344 ms |
10324 KB |
Output is correct |
5 |
Correct |
157 ms |
12872 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
392 ms |
10712 KB |
Output is correct |
8 |
Correct |
74 ms |
5264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
4 ms |
604 KB |
Output is correct |
3 |
Correct |
6 ms |
604 KB |
Output is correct |
4 |
Correct |
4 ms |
604 KB |
Output is correct |
5 |
Correct |
5 ms |
600 KB |
Output is correct |
6 |
Correct |
7 ms |
604 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
6 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
404 KB |
Output is correct |
10 |
Correct |
4 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
2 ms |
348 KB |
Output is correct |
13 |
Correct |
7 ms |
604 KB |
Output is correct |
14 |
Correct |
7 ms |
604 KB |
Output is correct |
15 |
Correct |
7 ms |
604 KB |
Output is correct |
16 |
Correct |
7 ms |
604 KB |
Output is correct |
17 |
Correct |
4 ms |
348 KB |
Output is correct |
18 |
Correct |
2 ms |
348 KB |
Output is correct |
19 |
Correct |
6 ms |
628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
173 ms |
9056 KB |
Output is correct |
3 |
Correct |
374 ms |
12624 KB |
Output is correct |
4 |
Correct |
344 ms |
10324 KB |
Output is correct |
5 |
Correct |
157 ms |
12872 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
392 ms |
10712 KB |
Output is correct |
8 |
Correct |
74 ms |
5264 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
4 ms |
604 KB |
Output is correct |
11 |
Correct |
6 ms |
604 KB |
Output is correct |
12 |
Correct |
4 ms |
604 KB |
Output is correct |
13 |
Correct |
5 ms |
600 KB |
Output is correct |
14 |
Correct |
7 ms |
604 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
6 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
404 KB |
Output is correct |
18 |
Correct |
4 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
2 ms |
348 KB |
Output is correct |
21 |
Correct |
7 ms |
604 KB |
Output is correct |
22 |
Correct |
7 ms |
604 KB |
Output is correct |
23 |
Correct |
7 ms |
604 KB |
Output is correct |
24 |
Correct |
7 ms |
604 KB |
Output is correct |
25 |
Correct |
4 ms |
348 KB |
Output is correct |
26 |
Correct |
2 ms |
348 KB |
Output is correct |
27 |
Correct |
6 ms |
628 KB |
Output is correct |
28 |
Correct |
564 ms |
15848 KB |
Output is correct |
29 |
Correct |
579 ms |
15852 KB |
Output is correct |
30 |
Correct |
534 ms |
14040 KB |
Output is correct |
31 |
Correct |
470 ms |
12628 KB |
Output is correct |
32 |
Correct |
489 ms |
11092 KB |
Output is correct |
33 |
Correct |
229 ms |
10580 KB |
Output is correct |
34 |
Correct |
604 ms |
15520 KB |
Output is correct |
35 |
Correct |
454 ms |
12116 KB |
Output is correct |
36 |
Correct |
402 ms |
10696 KB |
Output is correct |
37 |
Correct |
620 ms |
12372 KB |
Output is correct |
38 |
Correct |
555 ms |
15440 KB |
Output is correct |
39 |
Correct |
205 ms |
11916 KB |
Output is correct |
40 |
Correct |
217 ms |
11712 KB |
Output is correct |
41 |
Correct |
206 ms |
10616 KB |
Output is correct |
42 |
Correct |
480 ms |
13740 KB |
Output is correct |
43 |
Correct |
554 ms |
13396 KB |
Output is correct |
44 |
Correct |
61 ms |
5468 KB |
Output is correct |