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][(C+63)/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 <Math.min(C-j,64); k++) {
if(j+k<C && s.charAt(j+k)=='.'){
map[i][j/64]|=(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[(C+63)/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[(C+63)/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+63)/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+63)/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][(C+63)/64];
long[] b=new long[(C+63)/64];
for (int j = 0; j <R; j++) {
a[j]=shift(dp[j],1,j,a[j]);
b=shift(dp[j],-1,j,b).clone();
for (int k = 0; k <(C+63)/64; k++) {
a[j][k]|=b[k];
}
if(j>0){
for (int k = 0; k <(C+63)/64; k++) {
a[j][k]|=dp[j-1][k];
}
}
if(j<R-1){
for (int k = 0; k <(C+63)/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+63)/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+63)/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=(63+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+63)/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 |
Correct |
121 ms |
10560 KB |
Output is correct |
| 2 |
Correct |
123 ms |
10408 KB |
Output is correct |
| 3 |
Correct |
125 ms |
10524 KB |
Output is correct |
| 4 |
Correct |
128 ms |
10536 KB |
Output is correct |
| 5 |
Correct |
136 ms |
10580 KB |
Output is correct |
| 6 |
Correct |
126 ms |
10448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
10560 KB |
Output is correct |
| 2 |
Correct |
123 ms |
10408 KB |
Output is correct |
| 3 |
Correct |
125 ms |
10524 KB |
Output is correct |
| 4 |
Correct |
128 ms |
10536 KB |
Output is correct |
| 5 |
Correct |
136 ms |
10580 KB |
Output is correct |
| 6 |
Correct |
126 ms |
10448 KB |
Output is correct |
| 7 |
Incorrect |
127 ms |
10644 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
10560 KB |
Output is correct |
| 2 |
Correct |
123 ms |
10408 KB |
Output is correct |
| 3 |
Correct |
125 ms |
10524 KB |
Output is correct |
| 4 |
Correct |
128 ms |
10536 KB |
Output is correct |
| 5 |
Correct |
136 ms |
10580 KB |
Output is correct |
| 6 |
Correct |
126 ms |
10448 KB |
Output is correct |
| 7 |
Incorrect |
127 ms |
10644 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
