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>
using namespace std;
#define dbg(x) cerr << #x << ": " << x << endl;
const int MAX_N = 500 + 5;
const int MAX_M = 5000 + 5;
string a[MAX_N];
bitset<MAX_M> used[MAX_N][MAX_N];
bitset<MAX_M> res[MAX_N][MAX_N];
pair<int, int> delta[] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
mt19937 rng(random_device{}());
bool can(int i, int j, int pos, int n, int m, const string& s) {
if (i < 0 || i >= n || j < 0 || j >= m || a[i][j] == '#') {
return false;
}
if (used[i][j].test(pos)) {
return res[i][j].test(pos);
}
if (pos == (int)s.size()) {
res[i][j].set(pos);
return true;
}
auto c = s[pos];
used[i][j].set(pos);
if (c == 'N') {
res[i][j][pos] = can(i - 1, j, pos + 1, n, m, s);
} else if (c == 'S') {
res[i][j][pos] = can(i + 1, j, pos + 1, n, m, s);
} else if (c == 'W') {
res[i][j][pos] = can(i, j - 1, pos + 1, n, m, s);
} else if (c == 'E') {
res[i][j][pos] = can(i, j + 1, pos + 1, n, m, s);
} else {
// shuffle(begin(delta), end(delta), rng);
for (const auto& [di, dj] : delta) {
// dbg(di);
// dbg(dj);
res[i][j].set(pos, can(i + di, j + dj, pos + 1, n, m, s));
if (res[i][j].test(pos)) return true;
}
}
return res[i][j][pos];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, t;
cin >> n >> m >> t;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
string s;
cin >> s;
reverse(s.begin(), s.end());
for (auto& c : s) {
if (c == 'N') {
c = 'S';
} else if (c == 'S') {
c = 'N';
} else if (c == 'W') {
c = 'E';
} else if (c == 'E') {
c = 'W';
}
}
int ans = 0;
// reverse the operations and check if there exists at least one starting position
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i][j] == '#') continue;
if (can(i, j, 0, n, m, s)) ++ans;
}
}
cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |