#include <bits/stdc++.h>
using namespace std;
const int kN = 500;
bitset<kN> grid[1 + kN + 1];
bitset<kN> dp[2][1 + kN + 1];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, p;
cin >> n >> m >> p;
for (int i = 1; i <= n; ++i) {
string s;
cin >> s;
for (int j = 0; j < m; ++j) {
if (s[j] == '.') {
grid[i].set(j);
}
}
}
string moves;
cin >> moves;
for (int i = 1; i <= n; ++i) {
dp[0][i] = grid[i];
}
int t = 0;
for (int step = 0; step < p; ++step, t ^= 1) {
for (int i = 1; i <= n; ++i) {
dp[t ^ 1][i].reset();
if (moves[step] == 'N' || moves[step] == '?') {
dp[t ^ 1][i] |= dp[t][i + 1];
}
if (moves[step] == 'E' || moves[step] == '?') {
dp[t ^ 1][i] |= dp[t][i] << 1;
}
if (moves[step] == 'S' || moves[step] == '?') {
dp[t ^ 1][i] |= dp[t][i - 1];
}
if (moves[step] == 'W' || moves[step] == '?') {
dp[t ^ 1][i] |= dp[t][i] >> 1;
}
dp[t ^ 1][i] &= grid[i];
}
}
int res = 0;
for (int i = 1; i <= n; ++i) {
res += dp[t][i].count();
}
cout << res << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
80 ms |
420 KB |
Output is correct |
23 |
Correct |
71 ms |
420 KB |
Output is correct |
24 |
Correct |
69 ms |
340 KB |
Output is correct |
25 |
Correct |
68 ms |
340 KB |
Output is correct |
26 |
Correct |
68 ms |
404 KB |
Output is correct |
27 |
Correct |
103 ms |
416 KB |
Output is correct |
28 |
Correct |
103 ms |
340 KB |
Output is correct |
29 |
Correct |
103 ms |
424 KB |
Output is correct |
30 |
Correct |
101 ms |
424 KB |
Output is correct |
31 |
Correct |
99 ms |
340 KB |
Output is correct |
32 |
Correct |
133 ms |
420 KB |
Output is correct |
33 |
Correct |
127 ms |
340 KB |
Output is correct |
34 |
Correct |
127 ms |
340 KB |
Output is correct |
35 |
Correct |
129 ms |
340 KB |
Output is correct |
36 |
Correct |
123 ms |
340 KB |
Output is correct |