#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define ii pair<int , int>
#define iv pair<ii , ii>
#define iii pair<int , ii>
#define fi first
#define se second
#define int long long
const int inf = 1e18 + 7;
const int MAX_N = 5e2 + 7;
const int MOD = 1e9 + 7;
char a[MAX_N][MAX_N];
int f[MAX_N][MAX_N][100];
char s[5007];
signed main() {
ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
int n , m , l; cin >> n >> m >> l;
//subtask 1&2
if (n <= 100 && m <= 100 && l <= 100) {
for (int i = 1 ; i <= n ; i++) {
for (int j = 1 ; j <= m ; j++) {
cin >> a[i][j];
}
}
for (int i = 1 ; i <= l ; i++) {
cin >> s[i];
}
for (int i = 1 ; i <= n ; i++) {
for (int j = 1 ; j <= m ; j++) {
if (a[i][j] != '#') {
f[i][j][0] = 1;
}
}
}
for (int h = 1 ; h <= l ; h++) {
for (int i = 1 ; i <= n ;i ++) {
for (int j = 1 ; j <= m ; j++) {
if (a[i][j] == '#') continue;;
if (s[h] == 'W' && j < m) {
f[i][j][h] = f[i][j + 1][h - 1];
}
if (s[h] == 'N' && i < n) {
f[i][j][h] = f[i + 1][j][h - 1];
}
if (s[h] == 'E' && 1 < j) {
f[i][j][h] = f[i][j - 1][h - 1];
}
if (s[h] == 'S' && 1 < i) {
f[i][j][h] = f[i - 1][j][h - 1];
}
if (s[h] == '?') {
if (j < m && f[i][j + 1][h - 1]) f[i][j][h] = f[i][j + 1][h - 1];
if (i < n && f[i + 1][j][h - 1]) f[i][j][h] = f[i + 1][j][h - 1];
if (1 < j && f[i][j - 1][h - 1]) f[i][j][h] = f[i][j - 1][h - 1];
if (1 < i && f[i - 1][j][h - 1]) f[i][j][h] = f[i - 1][j][h - 1];
}
}
}
}
int ans = 0;
int cnt = 0;
for (int i = 1 ; i <= n ;i ++) {
for (int j = 1 ; j <= m ; j++) {
if (f[i][j][l]) {
ans++;
}
//cout << f[i][j][l] << " ";
}
//cout << '\n';
}
cout << ans;
}
else {
//subtask 3
bitset<5007> f[2][MAX_N];
bitset<5007> d[MAX_N];
for (int i = 0 ; i < n ; i++) {
d[i].flip();
f[1][i].flip();
for (int j = 0 ; j < m ; j++) {
cin >> a[i][j];
if (a[i][j] == '#') {
d[i][j].flip();
f[1][i][j].flip();
}
}
}
for (int i = 0 ; i < l ; i++) {
cin >> s[i];
}
for (int i = 0 ; i < l ; i++) {
int now = i & 1;
int prev = now ^ 1;
for (int j = 0 ; j < n ; j++) {
if (s[i] == 'W') {
f[now][j] = f[prev][j] << 1;
}
if (s[i] == 'E') {
f[now][j] = f[prev][j] >> 1;
}
if (s[i] == 'S') {
f[now][j] = f[prev][j - 1];
}
if (s[i] == 'N') {
f[now][j] = f[prev][j + 1];
}
if (s[i] == '?') {
f[now][j] |= f[prev][j - 1];
f[now][j] |= f[prev][j + 1];
f[now][j] |= (f[prev][j] >> 1);
f[now][j] |= (f[prev][j] << 1);
}
f[now][j] = f[now][j] & d[j];
}
for (int j = 0 ; j < n ; j++) {
f[prev][j] = f[now][j];
}
}
int ans = 0;
for (int i = 0 ; i < n ; i++) {
for (int j = 0 ; j < m ; j++) {
if (f[(l - 1) & 1][i][j]) {
ans++;
}
}
}
cout << ans;
}
return 0;
}
Compilation message
nautilus.cpp: In function 'int main()':
nautilus.cpp:70:13: warning: unused variable 'cnt' [-Wunused-variable]
70 | int cnt = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
9556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
9556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
9556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
