Submission #703474

#TimeUsernameProblemLanguageResultExecution timeMemory
703474bebraNautilus (BOI19_nautilus)C++17
29 / 100
2 ms340 KiB
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;

const int MAX_N = 500 + 5;
string a[MAX_N];


bool can(int i, int j, int n, int m, const string& s) {
    for (auto c : s) {
        if (c == 'N') {
            --i;
        } else if (c == 'S') {
            ++i;
        } else if (c == 'W') {
            --j;
        } else {
            ++j;
        }
        if (i < 0 || i >= n || j < 0 || j >= m || a[i][j] == '#') {
            return false;
        }
    }
    return true;
}

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 {
            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, n, m, s)) ++ans;
        }
    }
    cout << ans << '\n';

    
    return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...