# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
857179 | Trisanu_Das | Nautilus (BOI19_nautilus) | C++17 | 0 ms | 0 KiB |
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;
int r, c, m;
string a[100], s;
int main(){
cin >> r >> c >> m;
for(int i = 0; i < r; i++) cin >> a[i];
cin >> s;
bitset<1000> dp[r], temp[r], aa[r];
for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) dp[i][j] = aa[i][j] = a[i][c - j - 1];
for(auto dir : s){
for(int i = 0; i < r; i++){
if(dir == 'N') {
if(i + 1 < r) dp[i] = dp[i + 1] & aa[i];
else dp[i].reset();
}
if(dir == 'E') dp[i] = (dp[i] >> 1) & aa[i];
if(dir == 'W') dp[i] = (dp[i] << 1) & aa[i];
if(dir == '?'){
temp[i] = (reach[i] >> 1) | (reach[i] << 1);
if(i) temp[i] |= reach[i -1];
if(i + 1 < r) temp[i] |= reach[i + 1];
temp[i] &= aa[i];
}
}
for(int i = r - 1; i > -1; i--){
if(w == 'S'){
if(i) reach[i] = reach[i - 1] & aa[i];
else reach[i].reset();
}
}
for(int i = 0; i < r; i++) if(w == '?') reach[i] = temp[i];
}
int ans = 0;
for(int i = 0; i < r; i++) ans += reach.count();
cout << ans << '\n';
}