// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
const int nax = 505;
using B = bitset<nax>;
template<class T> using V = vector<T>;
using vi = V<int>;
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, M, K; cin >> N >> M >> K;
V<B> A(N); for(int i = 0; i < N; i++) {
string S; cin >> S;
for(int j = 0; j < M; j++) A[i][j] = (S[j] == '.');
}
string O; cin >> O;
V<V<B>> dp(K+1, V<B>(N));
for(int i = 0; i < N; i++) dp[0][i] = A[i];
auto perform = [&](int i, char c) {
if (c == 'N') for(int r = 1; r < N; r++) dp[i + 1][r - 1] |= dp[i][r] & A[r - 1];
if (c == 'S') for(int r = 0; r < N - 1; r++) dp[i + 1][r + 1] |= dp[i][r] & A[r + 1];
if (c == 'W') for(int r = 0; r < N; r++) dp[i + 1][r] |= (dp[i][r] >> 1) & A[r];
if (c == 'E') for(int r = 0; r < N; r++) dp[i + 1][r] |= (dp[i][r] << 1) & A[r];
};
for(int i = 0; i < K; i++) {
if (O[i] == '?') for(auto& c : "NWES") perform(i, c);
else perform(i, O[i]);
// cout << "OPER: " << i << " " << O[i] << endl;
// for(int r = 0; r < N; r++) {
// for(int c = 0; c < M; c++) cout << dp[i][r][c];
// cout << nl;
// }
}
int ans = 0;
// for(int r = 0; r < N; r++) {
// for(int c = 0; c < M; c++) cout << dp.back()[r][c];
// cout << nl;
// }
for(int r = 0; r < N; r++) ans += dp.back()[r].count();
cout << ans << nl;
exit(0-0);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1116 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 10 |
Correct |
1 ms |
976 KB |
Output is correct |
| 11 |
Correct |
1 ms |
860 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 17 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 18 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 19 |
Correct |
2 ms |
1272 KB |
Output is correct |
| 20 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 21 |
Correct |
1 ms |
1116 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 10 |
Correct |
1 ms |
976 KB |
Output is correct |
| 11 |
Correct |
1 ms |
860 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 13 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 14 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 15 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 17 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 18 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 19 |
Correct |
2 ms |
1272 KB |
Output is correct |
| 20 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 21 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 22 |
Correct |
126 ms |
157520 KB |
Output is correct |
| 23 |
Correct |
123 ms |
157524 KB |
Output is correct |
| 24 |
Correct |
122 ms |
157408 KB |
Output is correct |
| 25 |
Correct |
120 ms |
157560 KB |
Output is correct |
| 26 |
Correct |
121 ms |
157528 KB |
Output is correct |
| 27 |
Correct |
152 ms |
157560 KB |
Output is correct |
| 28 |
Correct |
155 ms |
157524 KB |
Output is correct |
| 29 |
Correct |
156 ms |
157524 KB |
Output is correct |
| 30 |
Correct |
161 ms |
157524 KB |
Output is correct |
| 31 |
Correct |
158 ms |
157780 KB |
Output is correct |
| 32 |
Correct |
180 ms |
157400 KB |
Output is correct |
| 33 |
Correct |
180 ms |
157524 KB |
Output is correct |
| 34 |
Correct |
178 ms |
157556 KB |
Output is correct |
| 35 |
Correct |
175 ms |
157552 KB |
Output is correct |
| 36 |
Correct |
181 ms |
157556 KB |
Output is correct |
