제출 #920737

#제출 시각아이디문제언어결과실행 시간메모리
92073712345678Nautilus (BOI19_nautilus)C++17
100 / 100
186 ms1104 KiB
#include <bits/stdc++.h>

using namespace std;

const int nx=505;
int r, c, m, cnt;
char mp[nx][nx];
bitset<nx> dp[2][nx], w[nx];
string s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>r>>c>>m;
    for (int i=1; i<=r; i++) for (int j=1; j<=c; j++) cin>>mp[i][j], w[i][j]=(mp[i][j]!='#'), dp[0][i][j]=w[i][j];
    cin>>s;
    for (int i=1; i<=m; i++)
    {
        int cr=i%2, pv=1-cr;
        for (int j=1; j<=r; j++) dp[cr][j]=0;
        if (s[i-1]=='N'||s[i-1]=='?') for (int j=1; j<=r-1; j++) dp[cr][j]|=dp[pv][j+1];
        if (s[i-1]=='S'||s[i-1]=='?') for (int j=2; j<=r; j++) dp[cr][j]|=dp[pv][j-1];
        if (s[i-1]=='E'||s[i-1]=='?') for (int j=1; j<=r; j++) dp[cr][j]|=dp[pv][j]<<1;
        if (s[i-1]=='W'||s[i-1]=='?') for (int j=1; j<=r; j++) dp[cr][j]|=dp[pv][j]>>1;
        for (int j=1; j<=r; j++) dp[cr][j]&=w[j];
    }
    for (int i=1; i<=r; i++) for (int j=1; j<=c; j++) cnt+=dp[m%2][i][j];
    cout<<cnt;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...