Submission #1187574

#TimeUsernameProblemLanguageResultExecution timeMemory
1187574omerkingNautilus (BOI19_nautilus)C++20
66 / 100
1096 ms836 KiB
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int main(){
    int r,c,m;cin>>r>>c>>m;
    vector<string>a(r);
    for(int i=0;i<r;++i)cin>>a[i];
    string s;cin>>s;
    vector<vector<bool>>dp(r,vector<bool>(c));
    for(int i=0;i<r;++i)for(int j=0;j<c;++j)dp[i][j]=a[i][j]=='.';
    for(char ch:s){
        vector<vector<bool>>next(r,vector<bool>(c,false));
        for(int i=0;i<r;++i)for(int j=0;j<c;++j)if(dp[i][j]){
            for(int d=0;d<4;++d)if(ch=='?'||"NESW"[d]==ch){
                int ni=i+dx[d],nj=j+dy[d];
                if(ni>=0&&ni<r&&nj>=0&&nj<c&&a[ni][nj]=='.')next[ni][nj]=true;
            }
        }
        dp=next;
    }
    int ans=0;
    for(int i=0;i<r;++i)for(int j=0;j<c;++j)if(dp[i][j])++ans;
    cout<<ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...