import java.io.*; import java.util.*;
public class nautilus{
static class FastReader
{
BufferedReader br;
StringTokenizer st;
public FastReader()
{
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt()
{
return Integer.parseInt(next());
}
}
static int MOD=998244353;
static long[][] map,dp;
static int R,C;
public static void main(String[] args){
FastReader br=new FastReader();
R=br.nextInt(); C=br.nextInt();int M=br.nextInt();
map=new long[R][1+C/64]; String s;
for (int i = 0; i < R; i++) {//Setting up the map
s=br.next();
for (int j = 0; j < C; j+=64) {
for (int k = 0; k <64; k++) {
if(j+k<C && s.charAt(j+k)=='.'){
map[i][j]|=(long) 1<<k;
}
}
}
}
s=br.next();
dp=map.clone();//All positions are reachable with 0 moves
long[] ans;
for (int i = 0; i < M; i++) {
if(s.charAt(i)=='E'){//Shift right
for (int j = 0; j < R; j++) {
ans=new long[1+C/64];
dp[j]=shift(dp[j],1,j,ans);
}
}else if(s.charAt(i)=='W'){
for (int j = 0; j < R; j++) {
ans=new long[1+C/64];
dp[j]=shift(dp[j],-1,j,ans);
}
}else if(s.charAt(i)=='N'){
for (int j = 0; j < R-1; j++) {
dp[j]=dp[j+1].clone();
for (int k = 0; k <=C/64; k++) {
dp[j][k]&=map[j][k];
}
}
Arrays.fill(dp[R-1],0);
}else if(s.charAt(i)=='S'){
for (int j = R-1; j > 0; j--) {
dp[j]=dp[j-1].clone();
for (int k = 0; k <=C/64; k++) {
dp[j][k]&=map[j][k];
}
}
Arrays.fill(dp[0],0);
}else{//Take the OR of all four, then AND the map
long[][] a=new long[R][1+C/64];
long[] b=new long[1+C/64];
for (int j = 0; j <R; j++) {
a[j]=shift(dp[j],1,j,a[j]);
if(j==0){
System.out.println(a[j][0]);
}
b=shift(dp[j],-1,j,b).clone();
for (int k = 0; k <=C/64; k++) {
a[j][k]|=b[k];
}
if(j>0){
for (int k = 0; k <=C/64; k++) {
a[j][k]|=dp[j-1][k];
}
}
if(j<R-1){
for (int k = 0; k <=C/64; k++) {
a[j][k]|=dp[j+1][k];
}
}
//Do I need to make a[.][k] 0? No! They would not be affected because I have ORed them with the correct stuff.
for (int k = 0; k <=C/64; k++) {
a[j][k]&=map[j][k];
}
}
dp=a.clone();
}
}
int res=0;
for (int i = 0; i < R; i++) {
for (int j = 0; j <=C/64; j++) {
res+=Long.bitCount(dp[i][j]);
}
}
System.out.println(res);
}
public static long[] shift(long[] a, int c, int ind, long[] ans){
int len=1+C/64;
if(c==1){
long x=(long) 1<<63;
for (int i = 0; i < len-1; i++) {
long b=a[i]&(x-1);
ans[i]|=((long) b<<1);
long d=a[i]>>>63;//3>'s, 2>'s don't work
ans[i+1]|=d;
}
//Take care of last bit
ans[len-1]|=a[len-1]<<1;
}else{//c=-1
ans[0]=a[0]>>>1;
for (int i = 1; i < len; i++) {
long b=a[i]&1;
ans[i-1]|=((long)b<<63);
ans[i]|=a[i]>>>1;
}
}
for (int i = 0; i <=C/64; i++) {
ans[i]&=map[ind][i];
}
return ans;
}
}
//Debugging:
//Are you sure your algorithm is correct?
//Bounds: long
//Special cases: n=0,1?
//Make sure you remove your debugging code before you submit!
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
74 ms |
8852 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
74 ms |
8852 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
74 ms |
8852 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
