제출 #535203

#제출 시각아이디문제언어결과실행 시간메모리
535203__VariattoNautilus (BOI19_nautilus)C++17
66 / 100
1038 ms1476 KiB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=5e3+10;
int n, m, k;
string curr, s;
bitset<MAX>dp[2][MAX], p[MAX];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1; i<=n; i++){
        cin>>curr;
        for(int j=1; j<=m; j++)
            if(curr[j-1]=='.')
                p[i][j]=dp[1][i][j]=1;
    }
    cin>>s;
    s='$'+s;
    int x=0;
    for(int i=1; i<=k; i++){
        for(int j=1; j<=n; j++)
            dp[x][j]&=0;
        if(s[i]=='?'||s[i]=='E')
            for(int j=1; j<=n; j++)
                dp[x][j]=(dp[x][j]|(dp[!x][j]<<1));
        if(s[i]=='?'||s[i]=='W')
            for(int j=1; j<=n; j++)
                dp[x][j]=(dp[x][j]|(dp[!x][j]>>1));
        if(s[i]=='?'||s[i]=='N')
            for(int j=n-1; j>=1; j--)
                dp[x][j]=(dp[x][j]|dp[!x][j+1]);
        if(s[i]=='?'||s[i]=='S')
            for(int j=2; j<=n; j++)
                dp[x][j]=(dp[x][j]|dp[!x][j-1]);
        for(int j=1; j<=n; j++)
            dp[x][j]&=p[j];
        x=!x;
    }
    int wynik=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            wynik+=dp[!x][i][j];
    cout<<wynik<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...