Submission #1135211

#TimeUsernameProblemLanguageResultExecution timeMemory
1135211alir3za_zar3Nautilus (BOI19_nautilus)C++20
100 / 100
129 ms848 KiB
// Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
#define   loop(i , l , r)    for (int i=l; i<=r; i+=1)
#define    arc(i , r , l)    for (int i=r; i>=l; i-=1)

const int N = 5e2+7;
bitset<N> dp[2][N],null[N];
string s,t[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);
 
    int r,c,m; cin >> r >> c >> m;
    loop(i,0,r-1)
    { 
        cin >> t[i]; 
        loop(j,0,c-1)
        {
            if (t[i][j]=='.')
            {
                dp[0][i][j] = 1; 
            }
            else 
            {
                null[i][j] = 1;
            }
        }
    } 
    cin >> s; int T=0;
    loop(k,0,m-1)
    {
        T = 1-T;
        bitset<N> update[N];
        if (s[k]=='?' or s[k]=='E')
        {
            loop(i,0,r-1)
            {
                update[i] |= dp[1-T][i]<<1;
                update[i][c] = 0;
            }
        } 
        if (s[k]=='?' or s[k]=='W')
        {
            loop(i,0,r-1)
            {
                update[i] |= dp[1-T][i]>>1;
            }
        } 
        if (s[k]=='?' or s[k]=='S')
        {
            loop(i,1,r-1)
            {
                update[i] |= dp[1-T][i-1];
            } 
        }
        if (s[k]=='?' or s[k]=='N')
        {
            loop(i,0,r-2)
            {
                update[i] |= dp[1-T][i+1];
            } 
        }

        loop(i,0,r-1)
        {
            update[i] ^= update[i]&null[i];
            dp[T][i] = update[i];
        }
    }
    int out = 0;
    loop(i,0,r-1)
    {
        loop(j,0,c-1)
        {
            out += (dp[T][i][j]==1);
        } 
    }
    cout << out << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...