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>
#define prev prevw313131313
#define next next131313131
#define pb push_back
using namespace std;
const int MAXN = 505;
char tp[MAXN][MAXN];
bool dp[2][MAXN][MAXN];
int toY[] = {-1, 0, 1, 0};
int toX[] = {0, 1, 0, -1};
bool in(int y, int x, int r, int c) {
return 1 <= y && y <= r && 1 <= x && x <= c;
}
int pos[1000];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int r, c, m;
cin >> r >> c >> m;
pos['N'] = 0;
pos['E'] = 1;
pos['S'] = 2;
pos['W'] = 3;
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
cin >> tp[i][j];
}
}
string mp;
cin >> mp;
mp = ' ' + mp;
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
if (tp[i][j] == '.') {
dp[0][i][j] = 1;
}
}
}
// 0 moves
for (int step = 1; step <= m; step++) {
int prev = ((step - 1) & 1);
int cur = (step & 1);
for (int y = 1; y <= r; y++) {
for (int x = 1; x <= c; x++) {
dp[cur][y][x] = 0;
}
}
vector <int> possible;
if (mp[step] == '?') {
for (int k = 0; k < 4; k++) {
possible.pb(k);
}
} else {
possible.pb(pos[mp[step]]);
}
for (int y = 1; y <= r; y++) {
for (int x = 1; x <= c; x++) {
if (dp[prev][y][x]) {
for (int el : possible) {
int nY = y + toY[el];
int nX = x + toX[el];
if (in(nY, nX, r, c) && tp[nY][nX] == '.') {
dp[cur][nY][nX] = 1;
}
}
}
}
}
}
int ans = 0;
for (int y = 1; y <= r; y++) {
for (int x = 1; x <= c; x++) {
ans += dp[m % 2][y][x];
}
}
cout << ans << endl;
}
/*
5 9 7
...##....
..#.##..#
..#....##
.##...#..
....#....
WS?EE??
*/
Compilation message (stderr)
nautilus.cpp: In function 'int main()':
nautilus.cpp:61:28: warning: array subscript has type 'char' [-Wchar-subscripts]
61 | possible.pb(pos[mp[step]]);
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |