Submission #923832

#TimeUsernameProblemLanguageResultExecution timeMemory
923832KarootNautilus (BOI19_nautilus)C++17
100 / 100
231 ms1108 KiB
#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
#include <bitset>

#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;

ll linf = 1e15+1;

inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

int main(){
    scoobydoobydoo();
    int r, c, m; cin >> r >> c >> m;
    bitset<(int)3e5> bs;
    bitset<(int)3e5> allowed;
    int counter = 0;
    for (int i = 0; i < r; i++){
        for (int j = 0; j < c; j++){
            char e; cin >> e;
            if (e == '.')allowed[counter] = 1;
            counter++;
        }
    }

    bs |= allowed;

    //for (int i = 0; i < counter; i++)cout << bs[i] << " ";
    //cout << endl;

    //mask to right
    int cnt = 0;
    bitset<(int)3e5> maskR;
    for (int i = 0; i < r; i++){
        for (int j = 0; j < c-1; j++){
            maskR[cnt++] = 1;
        }
        cnt++;
    }

    bitset<(int)3e5> maskL;
    cnt = 0;
    for (int i = 0; i < r; i++){
        cnt++;
        for (int j = 1; j < c; j++){
            maskL[cnt++] = 1;
        }
    }

    bitset<(int)3e5> maskU;
    cnt = c;
    for (int i = 1; i < r; i++){
        for (int j = 0; j < c; j++){
            maskU[cnt++] = 1;
        }
    }

    bitset<(int)3e5> maskD;
    cnt = 0;
    for (int i = 0; i < r-1; i++){
        for (int j = 0; j < c; j++){
            maskD[cnt++] = 1;
        }
    }


    string s; cin >> s;

    for (auto& e : s){
        /*cout << "------------" << endl << endl;
        for (int i = 0; i < counter; i++){
            cout << bs[i] << " ";
            if (i%c == c-1)cout << endl;
        }
        cout << "------------" << endl;*/
        if (e == 'W'){
            bs &= maskL;
            /*cout << "MASKL" << endl << endl;
            for (int i = 0; i < counter; i++){
                cout << bs[i] << " ";
                if (i%c == c-1)cout << endl;
            }
            cout << "------------" << endl;*/
            bs >>= 1;
            bs &= allowed;
        } else if (e == 'E'){
            bs &= maskR;
            bs <<= 1;
            bs &= allowed;
        } else if (e == 'N'){
            bs &= maskU;
            bs >>= c;
            bs &= allowed;
        } else if (e == 'S'){
            bs &= maskD;
            bs <<= c;
            bs &= allowed;
        } else {
            bs = ((bs&maskL) >> 1) | ((bs&maskR) << 1) | ((bs&maskU) >> c) | ((bs&maskD) << c);
            bs &= allowed;
        }
        /*cout << e << endl;
        for (int i = 0; i < counter; i++){
            cout << bs[i] << " ";
            if (i%c == c-1)cout << endl;
        }
        cout << "------------" << endl << endl;*/
    }

    ll sum = 0;

    for (int i = 0; i < counter; i++){
        sum += bs[i];
    }

    cout << sum << endl;

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