This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#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];
int dp[2][MAXN][MAXN];
int used_id = 1;
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];
bool possible[4];
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] = used_id;
}
}
}
// 0 moves
for (int step = 1; step <= m; step++) {
int prev = ((step - 1) & 1);
int cur = (step & 1);
for (int k = 0; k < 4; k++) {
possible[k] = 0;
}
if (mp[step] == '?') {
for (int k = 0; k < 4; k++) {
possible[k] = 1;
}
} else {
possible[pos[mp[step]]] = 1;
}
bool live = false;
for (int y = 1; y <= r; y++) {
for (int x = 1; x <= c; x++) {
if (dp[prev][y][x] == used_id) {
for (int cc = 0; cc < 4; cc++) {
if (!possible[cc]) {
continue;
}
int nY = y + toY[cc];
int nX = x + toX[cc];
if (in(nY, nX, r, c) && tp[nY][nX] == '.') {
dp[cur][nY][nX] = used_id + 1;
live = true;
}
}
}
}
}
if (!live) {
used_id = 1e9;
break;
}
used_id++;
}
int ans = 0;
for (int y = 1; y <= r; y++) {
for (int x = 1; x <= c; x++) {
ans += (dp[(m & 1)][y][x] == used_id);
}
}
cout << ans << endl;
}
/*
5 9 7
...##....
..#.##..#
..#....##
.##...#..
....#....
WS?EE??
*/
Compilation message (stderr)
nautilus.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization ("O3")
|
nautilus.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
3 | #pragma GCC optimization ("unroll-loops")
|
nautilus.cpp: In function 'int main()':
nautilus.cpp:62:25: warning: array subscript has type 'char' [-Wchar-subscripts]
62 | possible[pos[mp[step]]] = 1;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |