#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
bitset <505> dp[505][5005], grid[505];
void Solve()
{
int n, m, q; cin >> n >> m >> q;
vector <string> a(n);
for (auto &x : a) cin >> x;
string s; cin >> s;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
if (a[i - 1][j - 1] == '.') {
grid[i][j] = 1;
dp[i][0][j] = 1;
}
}
}
int c = 1;
for (auto &x : s){
for (int i = 1; i <= n; i++){
if (x == 'N' || x == '?') dp[i][c] |= (dp[i + 1][c - 1] & grid[i]);
if (x == 'S' || x == '?') dp[i][c] |= (dp[i - 1][c - 1] & grid[i]);
if (x == 'E' || x == '?') dp[i][c] |= ((dp[i][c - 1] << 1) & grid[i]);
if (x == 'W' || x == '?') dp[i][c] |= ((dp[i][c - 1] >> 1) & grid[i]);
}
c++;
}
int ans = 0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
ans += dp[i][q][j];
}
}
cout << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
// cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 15 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 17 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 18 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 19 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 20 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 21 |
Correct |
2 ms |
1364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 15 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 17 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 18 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 19 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 20 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 21 |
Correct |
2 ms |
1364 KB |
Output is correct |
| 22 |
Correct |
119 ms |
157460 KB |
Output is correct |
| 23 |
Correct |
137 ms |
157532 KB |
Output is correct |
| 24 |
Correct |
117 ms |
157576 KB |
Output is correct |
| 25 |
Correct |
118 ms |
157492 KB |
Output is correct |
| 26 |
Correct |
118 ms |
157456 KB |
Output is correct |
| 27 |
Correct |
153 ms |
157476 KB |
Output is correct |
| 28 |
Correct |
159 ms |
157512 KB |
Output is correct |
| 29 |
Correct |
153 ms |
157512 KB |
Output is correct |
| 30 |
Correct |
157 ms |
157540 KB |
Output is correct |
| 31 |
Correct |
173 ms |
157520 KB |
Output is correct |
| 32 |
Correct |
183 ms |
157532 KB |
Output is correct |
| 33 |
Correct |
184 ms |
157544 KB |
Output is correct |
| 34 |
Correct |
176 ms |
157552 KB |
Output is correct |
| 35 |
Correct |
197 ms |
157580 KB |
Output is correct |
| 36 |
Correct |
192 ms |
157552 KB |
Output is correct |
