Submission #1319194

#TimeUsernameProblemLanguageResultExecution timeMemory
1319194penguin133Nautilus (BOI19_nautilus)C++17
66 / 100
1095 ms824 KiB
// Source: https://usaco.guide/general/io

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

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