#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 500;
const int SZ = (N + 2) * (N + 2);
bitset<SZ> dp[5001];
bitset<SZ> cant;
int n, m, q;
char a[555][555];
int num[555][555], T;
string s;
int in(int i, int j){
return (i >= 1 && j >= 1 && i <= n && j <= m and a[i][j] == '.');
}
map<char, vector<pair<int, int> > > dir;
void zero_traps(bitset<SZ> &new_dp){
for(int i = 0;i <= n+1; i++){
for(int j = 0;j <= m + 1; j++){
if(a[i][j] == '#'){
new_dp[num[i][j]] = 0;
}
}
}
}
main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> q;
for(int i = 0;i <= n + 1; i++){
for(int j = 0;j <= m+1; j++){
if(i >= 1 && j >= 1 && i <= n && j <= m) cin >> a[i][j];
else a[i][j] = '#';
num[i][j] = T++;
if(a[i][j] == '#') cant[num[i][j]] = 1;
else dp[0][num[i][j]] = 1;
// if(i >= 1 && j >= 1 && i <= n && j <= m)
// cout << num[i][j] << ' ';
}
// cout << '\n';
}
dir['N'].push_back({-1, 0});
dir['S'].push_back({1, 0});
dir['E'].push_back({0, 1});
dir['W'].push_back({0, -1});
dir['?'].push_back({-1, 0});
dir['?'].push_back({1, 0});
dir['?'].push_back({0, 1});
dir['?'].push_back({0, -1});
cin >> s;
s = "#" + s;
// cout << s << '\n';
for(int round = 1; round <= q; round++){
char ch = s[round];
// cout << ch << " = ";
bitset<SZ> new_dp;
// if(ch == 'N'){
// new_dp = dp[0] & (new_dp >> (m + 2));
// }else if(ch == 'S'){
// new_dp = dp[0] & (new_dp << (m + 2));
// }else if(ch == 'E'){
// new_dp = dp[0] & (new_dp << 1);
// }else if(ch == 'W'){
// new_dp = dp[0] & (new_dp >> 1);
// }else{
// new_dp = (new_dp >> 1) | (new_dp << 1) | (new_dp << (m + 2)) | (new_dp >> (m + 2));
// new_dp = (new_dp & dp[0]);
// }
for(auto [x, y] : dir[ch]){
int k = x * (m + 2) + y;
if(k < 0){
k = -k;
new_dp |= (dp[round-1]>>k);
}else new_dp |=(dp[round-1] << k);
}
// cout << '\n';
dp[round] = (new_dp & dp[0]);
}
cout << dp[q].count();
return 0;
}
Compilation message
nautilus.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
33 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6876 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6812 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6876 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6812 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 7 |
Correct |
4 ms |
6744 KB |
Output is correct |
| 8 |
Correct |
3 ms |
6744 KB |
Output is correct |
| 9 |
Correct |
3 ms |
7000 KB |
Output is correct |
| 10 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 11 |
Correct |
3 ms |
6880 KB |
Output is correct |
| 12 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 13 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 14 |
Correct |
3 ms |
6744 KB |
Output is correct |
| 15 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 16 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 17 |
Correct |
4 ms |
6872 KB |
Output is correct |
| 18 |
Correct |
4 ms |
6744 KB |
Output is correct |
| 19 |
Correct |
4 ms |
6876 KB |
Output is correct |
| 20 |
Correct |
4 ms |
6748 KB |
Output is correct |
| 21 |
Correct |
4 ms |
6876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 4 |
Correct |
2 ms |
6876 KB |
Output is correct |
| 5 |
Correct |
2 ms |
6812 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 7 |
Correct |
4 ms |
6744 KB |
Output is correct |
| 8 |
Correct |
3 ms |
6744 KB |
Output is correct |
| 9 |
Correct |
3 ms |
7000 KB |
Output is correct |
| 10 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 11 |
Correct |
3 ms |
6880 KB |
Output is correct |
| 12 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 13 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 14 |
Correct |
3 ms |
6744 KB |
Output is correct |
| 15 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 16 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 17 |
Correct |
4 ms |
6872 KB |
Output is correct |
| 18 |
Correct |
4 ms |
6744 KB |
Output is correct |
| 19 |
Correct |
4 ms |
6876 KB |
Output is correct |
| 20 |
Correct |
4 ms |
6748 KB |
Output is correct |
| 21 |
Correct |
4 ms |
6876 KB |
Output is correct |
| 22 |
Correct |
104 ms |
157248 KB |
Output is correct |
| 23 |
Correct |
95 ms |
157268 KB |
Output is correct |
| 24 |
Correct |
94 ms |
157268 KB |
Output is correct |
| 25 |
Correct |
94 ms |
157384 KB |
Output is correct |
| 26 |
Correct |
94 ms |
157264 KB |
Output is correct |
| 27 |
Correct |
129 ms |
157264 KB |
Output is correct |
| 28 |
Correct |
134 ms |
157268 KB |
Output is correct |
| 29 |
Correct |
130 ms |
157332 KB |
Output is correct |
| 30 |
Correct |
135 ms |
157524 KB |
Output is correct |
| 31 |
Correct |
127 ms |
157280 KB |
Output is correct |
| 32 |
Correct |
156 ms |
157268 KB |
Output is correct |
| 33 |
Correct |
176 ms |
157324 KB |
Output is correct |
| 34 |
Correct |
159 ms |
157268 KB |
Output is correct |
| 35 |
Correct |
157 ms |
157264 KB |
Output is correct |
| 36 |
Correct |
181 ms |
157268 KB |
Output is correct |
