Submission #1367163

#TimeUsernameProblemLanguageResultExecution timeMemory
1367163po_rag526Nautilus (BOI19_nautilus)C++20
66 / 100
1094 ms580 KiB
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;

const int N = 505;
bitset<N> dp[N], prevdp[N], w[N];
char c[N][N];
int n, m, k;
string s;

bool check(int i, int j) {
    if (i >= n or j >= m or i < 0 or j < 0 or c[i][j] == '#') return false;
    return true;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> c[i][j];
            if (c[i][j] == '.') prevdp[i][j] = 1, w[i][j] = 1;
        }
    }
    cin >> s;
    for (int i1 = 0; i1 < k; i1++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) dp[i][j] = 0;
        }
        for (int i = 0; i < n; i++) {
            if (s[i1] == 'N' or s[i1] == '?') {
                if (i - 1 >= 0) dp[i - 1] |= prevdp[i];
                //if (check(i - 1, j)) dp[i - 1][j] = 1;
            }
            if (s[i1] == 'S' or s[i1] == '?') {
                if (i + 1 < n) dp[i + 1] |= prevdp[i];
                //if (check(i + 1, j)) dp[i + 1][j] = 1;
            }
            if (s[i1] == 'W' or s[i1] == '?') {
                dp[i] |= prevdp[i] >> 1;
                //if (check(i, j - 1)) dp[i][j - 1] = 1;
            }
            if (s[i1] == 'E' or s[i1] == '?') {
                dp[i] |= prevdp[i] << 1;
                //if (check(i, j + 1)) dp[i][j + 1] = 1;
            }

        }
        for (int i = 0; i < n; i++) {
            dp[i] &= w[i];
        }

        swap(dp, prevdp);
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (prevdp[i][j]) cnt++;
        }
    }
    cout << cnt << endl;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...