//#include<iostream>
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int nax = 501;
char grid[nax][nax];
vector<vector<vector<int>>>dp(nax,vector<vector<int>>(nax,vector<int>(2, 0)));
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> grid[i][j];
}
}
string s;
cin >> s;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
dp[i][j][0] = (grid[i][j] == '.' ? 1 : 0);
}
}
for (int t = 1; t <= k; t++){
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (grid[i][j] == '#')continue;
dp[i][j][t % 2] = 0;
if (s[t - 1] == 'N' || s[t - 1] == '?'){
if (i != n - 1)dp[i][j][t % 2] |= dp[i + 1][j][!(t % 2)];
}
if (s[t - 1] == 'S' || s[t - 1] == '?'){
if (i)dp[i][j][t % 2] |= dp[i - 1][j][!(t % 2)];
}
if (s[t - 1] == 'E' || s[t - 1] == '?'){
if (j)dp[i][j][t % 2] |= dp[i][j - 1][!(t % 2)];
}
if (s[t - 1] == 'W' || s[t - 1] == '?'){
if (j != m - 1){
dp[i][j][t % 2] |= dp[i][j + 1][!(t % 2)];
}
}
}
}
}
int ans = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
ans += dp[i][j][k & 1];
}
}
cout << ans << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
14164 KB |
Output is correct |
2 |
Correct |
16 ms |
14164 KB |
Output is correct |
3 |
Correct |
18 ms |
14140 KB |
Output is correct |
4 |
Correct |
17 ms |
14164 KB |
Output is correct |
5 |
Correct |
14 ms |
14164 KB |
Output is correct |
6 |
Correct |
13 ms |
14128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
14164 KB |
Output is correct |
2 |
Correct |
16 ms |
14164 KB |
Output is correct |
3 |
Correct |
18 ms |
14140 KB |
Output is correct |
4 |
Correct |
17 ms |
14164 KB |
Output is correct |
5 |
Correct |
14 ms |
14164 KB |
Output is correct |
6 |
Correct |
13 ms |
14128 KB |
Output is correct |
7 |
Correct |
15 ms |
14164 KB |
Output is correct |
8 |
Correct |
18 ms |
14128 KB |
Output is correct |
9 |
Correct |
22 ms |
14124 KB |
Output is correct |
10 |
Correct |
14 ms |
14048 KB |
Output is correct |
11 |
Correct |
13 ms |
14056 KB |
Output is correct |
12 |
Correct |
17 ms |
14056 KB |
Output is correct |
13 |
Correct |
17 ms |
14164 KB |
Output is correct |
14 |
Correct |
18 ms |
14124 KB |
Output is correct |
15 |
Correct |
14 ms |
14124 KB |
Output is correct |
16 |
Correct |
12 ms |
14136 KB |
Output is correct |
17 |
Correct |
17 ms |
14060 KB |
Output is correct |
18 |
Correct |
17 ms |
14164 KB |
Output is correct |
19 |
Correct |
16 ms |
14124 KB |
Output is correct |
20 |
Correct |
17 ms |
14168 KB |
Output is correct |
21 |
Correct |
12 ms |
14164 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
14164 KB |
Output is correct |
2 |
Correct |
16 ms |
14164 KB |
Output is correct |
3 |
Correct |
18 ms |
14140 KB |
Output is correct |
4 |
Correct |
17 ms |
14164 KB |
Output is correct |
5 |
Correct |
14 ms |
14164 KB |
Output is correct |
6 |
Correct |
13 ms |
14128 KB |
Output is correct |
7 |
Correct |
15 ms |
14164 KB |
Output is correct |
8 |
Correct |
18 ms |
14128 KB |
Output is correct |
9 |
Correct |
22 ms |
14124 KB |
Output is correct |
10 |
Correct |
14 ms |
14048 KB |
Output is correct |
11 |
Correct |
13 ms |
14056 KB |
Output is correct |
12 |
Correct |
17 ms |
14056 KB |
Output is correct |
13 |
Correct |
17 ms |
14164 KB |
Output is correct |
14 |
Correct |
18 ms |
14124 KB |
Output is correct |
15 |
Correct |
14 ms |
14124 KB |
Output is correct |
16 |
Correct |
12 ms |
14136 KB |
Output is correct |
17 |
Correct |
17 ms |
14060 KB |
Output is correct |
18 |
Correct |
17 ms |
14164 KB |
Output is correct |
19 |
Correct |
16 ms |
14124 KB |
Output is correct |
20 |
Correct |
17 ms |
14168 KB |
Output is correct |
21 |
Correct |
12 ms |
14164 KB |
Output is correct |
22 |
Execution timed out |
1083 ms |
14488 KB |
Time limit exceeded |
23 |
Halted |
0 ms |
0 KB |
- |