Submission #1319199

#TimeUsernameProblemLanguageResultExecution timeMemory
1319199penguin133Nautilus (BOI19_nautilus)C++17
100 / 100
257 ms740 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

	int r, c, m;
bitset<505> bs[505], def[505];
char a[505][505];
inline int conv(int x, int y) {
    return (x - 1) * c + y;
}
int main() {
    cin >> r >> c >> m;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            cin >> a[i][j];
            bs[i][j] = def[i][j] = 1;
            if (a[i][j] == '#') bs[i][j] = def[i][j] = 0;
        }
    }
    for (int i = 1; i <= m; i++) {
        char x; cin >> x;
        bitset <505> ok[505];
        if (x == 'S' || x == '?') {
            for (int j = 2; j <= r; j++) {
                //impose [l1, r1] onto [l2, r2]
                ok[j] |= bs[j - 1];
            }
        }
        if (x == 'N' || x == '?') {
            for (int j = 1; j < r; j++) {
                ok[j] |= bs[j + 1];
            }
        }
        if (x == 'E' || x == '?') {
            for (int j = 1; j <= r; j++) {
                ok[j] |= (bs[j]<<(505-(c-1)-1)>>(505-(c-1)-1+1)<<2);
            }
        }
        if (x == 'W' || x == '?') {
            for (int j = 1; j <= r; j++) {
                ok[j] |= (bs[j]<<(505-(c)-1)>>(505-(c)-1+2)<<1);
            }
        }
        for (int j = 1; j <= r; j++) bs[j] = ok[j] & def[j];
        /*
        for (int a = 1; a <= r; a++) {
            for (int b = 1; b <= c; b++) cout << bs[a][b];
            cout << '\n';
        }
        cout << '\n';
        */
    }
    int ans = 0;
    for (int i = 1; i <= r; i++) ans += bs[i].count();
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...