#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
#define int long long
const int mod=998244353,mxn=500+5,lg=30,inf=1e18,minf=-1e18,Mxn=501*501;
int n,m,sz;
bitset<505*505>yes,l,r,clear;
int32_t main(){
fastio
cin>>n>>m>>sz;
for(int i=0;i<=n*(m+1);i++)l[i]=r[i]=true;
bitset<505*505>dp;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
char a;cin>>a;
if(a=='.')dp[i*m+j]=yes[i*m+j]=true;
else yes[i*m+j]=false;
clear[i*m+j]=true;
}
}
for(int i=0;i<505*505;i+=m){
l[i]=false;
r[i+m-1]=false;
}
string k;cin>>k;
for(int i=0;i<sz;i++){
bitset<505*505>cdp,gol,gor;
gol=dp&l;
gor=dp&r;
if(k[i]=='N'||k[i]=='?')cdp|=(dp>>m);
if(k[i]=='S'||k[i]=='?')cdp|=(dp<<m);
if(k[i]=='W'||k[i]=='?')cdp|=(gol>>1);
if(k[i]=='E'||k[i]=='?')cdp|=(gor<<1);
cdp&=yes;
swap(dp,cdp);
}
int sum=0;
for(int i=0;i<n;i++)for(int j=0;j<m;j++)sum+=dp[i*m+j];
cout<<sum;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
600 KB |
Output is correct |
| 2 |
Correct |
2 ms |
604 KB |
Output is correct |
| 3 |
Correct |
2 ms |
652 KB |
Output is correct |
| 4 |
Correct |
2 ms |
604 KB |
Output is correct |
| 5 |
Correct |
2 ms |
600 KB |
Output is correct |
| 6 |
Correct |
2 ms |
476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
600 KB |
Output is correct |
| 2 |
Correct |
2 ms |
604 KB |
Output is correct |
| 3 |
Correct |
2 ms |
652 KB |
Output is correct |
| 4 |
Correct |
2 ms |
604 KB |
Output is correct |
| 5 |
Correct |
2 ms |
600 KB |
Output is correct |
| 6 |
Correct |
2 ms |
476 KB |
Output is correct |
| 7 |
Correct |
2 ms |
604 KB |
Output is correct |
| 8 |
Correct |
2 ms |
728 KB |
Output is correct |
| 9 |
Correct |
3 ms |
604 KB |
Output is correct |
| 10 |
Correct |
3 ms |
604 KB |
Output is correct |
| 11 |
Correct |
2 ms |
856 KB |
Output is correct |
| 12 |
Correct |
3 ms |
604 KB |
Output is correct |
| 13 |
Correct |
3 ms |
604 KB |
Output is correct |
| 14 |
Correct |
3 ms |
648 KB |
Output is correct |
| 15 |
Correct |
3 ms |
604 KB |
Output is correct |
| 16 |
Correct |
3 ms |
652 KB |
Output is correct |
| 17 |
Correct |
3 ms |
600 KB |
Output is correct |
| 18 |
Correct |
3 ms |
600 KB |
Output is correct |
| 19 |
Correct |
3 ms |
604 KB |
Output is correct |
| 20 |
Correct |
3 ms |
604 KB |
Output is correct |
| 21 |
Correct |
3 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
600 KB |
Output is correct |
| 2 |
Correct |
2 ms |
604 KB |
Output is correct |
| 3 |
Correct |
2 ms |
652 KB |
Output is correct |
| 4 |
Correct |
2 ms |
604 KB |
Output is correct |
| 5 |
Correct |
2 ms |
600 KB |
Output is correct |
| 6 |
Correct |
2 ms |
476 KB |
Output is correct |
| 7 |
Correct |
2 ms |
604 KB |
Output is correct |
| 8 |
Correct |
2 ms |
728 KB |
Output is correct |
| 9 |
Correct |
3 ms |
604 KB |
Output is correct |
| 10 |
Correct |
3 ms |
604 KB |
Output is correct |
| 11 |
Correct |
2 ms |
856 KB |
Output is correct |
| 12 |
Correct |
3 ms |
604 KB |
Output is correct |
| 13 |
Correct |
3 ms |
604 KB |
Output is correct |
| 14 |
Correct |
3 ms |
648 KB |
Output is correct |
| 15 |
Correct |
3 ms |
604 KB |
Output is correct |
| 16 |
Correct |
3 ms |
652 KB |
Output is correct |
| 17 |
Correct |
3 ms |
600 KB |
Output is correct |
| 18 |
Correct |
3 ms |
600 KB |
Output is correct |
| 19 |
Correct |
3 ms |
604 KB |
Output is correct |
| 20 |
Correct |
3 ms |
604 KB |
Output is correct |
| 21 |
Correct |
3 ms |
604 KB |
Output is correct |
| 22 |
Correct |
76 ms |
860 KB |
Output is correct |
| 23 |
Correct |
80 ms |
1000 KB |
Output is correct |
| 24 |
Correct |
79 ms |
860 KB |
Output is correct |
| 25 |
Correct |
77 ms |
1000 KB |
Output is correct |
| 26 |
Correct |
75 ms |
1260 KB |
Output is correct |
| 27 |
Correct |
100 ms |
860 KB |
Output is correct |
| 28 |
Correct |
103 ms |
856 KB |
Output is correct |
| 29 |
Correct |
102 ms |
860 KB |
Output is correct |
| 30 |
Correct |
101 ms |
860 KB |
Output is correct |
| 31 |
Correct |
100 ms |
860 KB |
Output is correct |
| 32 |
Correct |
132 ms |
860 KB |
Output is correct |
| 33 |
Correct |
122 ms |
1108 KB |
Output is correct |
| 34 |
Correct |
121 ms |
860 KB |
Output is correct |
| 35 |
Correct |
121 ms |
856 KB |
Output is correct |
| 36 |
Correct |
119 ms |
860 KB |
Output is correct |
