This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
nautilus.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
33 | main(){
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |