Submission #643701

#TimeUsernameProblemLanguageResultExecution timeMemory
643701ParsaSNautilus (BOI19_nautilus)C++14
100 / 100
539 ms158748 KiB
// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
typedef long long ll;
const int N = 500 + 5, MOD = 1e9 + 7;
bitset<N> grid[N], mtc[N][N * 10];

void solve() {
    int n, m, k; cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        for (int j = 0; j < m; j++)
            grid[i][j] = s[j] == '.';
    }
    string s; cin >> s;
    for (int i = 0; i < n; i++) {
        mtc[i][0] = grid[i];
    }
    bitset<N> null = 0;
    s = '.' + s;

    for (int i = 1; i <= k; i++) {
        for (int ip = 0; ip < n; ip++) {
            if (s[i] == 'S' || s[i] == '?') {
                mtc[ip][i] = mtc[ip][i] | ((ip ? mtc[ip - 1][i - 1] : null) & grid[ip]);
            }
            if (s[i] == 'N' || s[i] == '?') {
                mtc[ip][i] = mtc[ip][i] | (mtc[ip + 1][i - 1] & grid[ip]);
            }
            if (s[i] == 'E' || s[i] == '?')
                mtc[ip][i] = (grid[ip] & (mtc[ip][i - 1] << 1)) | mtc[ip][i];
            if (s[i] == 'W' || s[i] == '?')
                mtc[ip][i] = mtc[ip][i] | (grid[ip] & (mtc[ip][i - 1] >> 1));
        }

    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += mtc[i][k].count();
    }
    cout << ans << endl;
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...