Here's my code
Code: Select all
#include<cstdio>
#include<queue>
#include<cstring>
/*0 for north,1 for east,2 for soth,3 for west*/
using namespace std;
int D[4][2]={0,-1,1,0,0,1,-1,0};
bool check[505][505][18];
int comb(bool sign[4])//returns of decimal equivalent dir array of each node,i.e if it's input
{ //NES,then direction combination is 1110,3 directions open,one close
int i,sum=0,pw=1; //this function returns its decimal equivalent
for(i=3; i>=0; i--)
{
if(sign[i]==true)
sum+=pw;
pw*=2;
}
return sum;
}
typedef struct{
bool dir[4];
}E;
typedef struct{
bool dir[4];//stores directions
int x,y,gen;
}P;
E inp[505][505];
int row,col;
queue<P>q;
E change(E so,int deg)//for every degree,rotates the direction 90 degree clockwise
{
int i;
E r;
if(deg==0) return so;//no rotation needed
for(i=1; i<=deg; i++)
{
r.dir[1]=so.dir[0];
r.dir[2]=so.dir[1];
r.dir[3]=so.dir[2];
r.dir[0]=so.dir[3];
so=r;
}
return r;
}
int BFS(void)
{
P source,ss,pp;
E c;
int g,xx,yy,rotate,i,j;
source.x=source.y=source.gen=0;
for(i=0; i<4; i++) source.dir[i]=inp[0][0].dir[i];
q.push(source);
int k=comb(source.dir);
check[0][0][k]=true;
while(!q.empty())
{
ss=q.front();
q.pop();
for(i=0; i<4; i++)
{
if(ss.dir[i])
{
xx=ss.x+D[i][0];yy=ss.y+D[i][1];
if(xx>=0 && yy>=0 && xx<col && yy<row)
{
pp.x=xx;pp.y=yy;pp.gen=ss.gen+1;
if(pp.x==col-1 && pp.y==row-1) return pp.gen;
c=change(inp[yy][xx],(ss.gen+1)%4);
int k1=comb(c.dir);
if(!check[yy][xx][k1])
{
for(j=0; j<4; j++) pp.dir[j]=c.dir[j];
q.push(pp);
check[yy][xx][k1]=true;
}
}
}
}
}
return -1;
}
int main()
{
int i,j,k,move;
char s[6];
while(scanf("%d%d",&row,&col)!=EOF)
{
for(i=0; i<row; i++)
{
for(j=0; j<col; j++)
{
for(k=0; k<4; k++) inp[i][j].dir[k]=false;//initialisation
scanf("%s",s);
for(k=0; s[k]; k++)
{
if(s[k]=='N') inp[i][j].dir[0]=true;
else if(s[k]=='E') inp[i][j].dir[1]=true;
else if(s[k]=='S') inp[i][j].dir[2]=true;
else if(s[k]=='W') inp[i][j].dir[3]=true;
}
if(i==row-1 && j==col-2) j++;
}
}
while(!q.empty()) q.pop();
memset(check,0,sizeof(check));
move=BFS();
if(move==-1) printf("no path to exit\n");
else printf("%d\n",move);
}
return 0;
}
Code: Select all
32 128
E
EW
NW
NSW
NE
NEW
E
NS
EW
EW
N
S
E
S
NS
NS
NEW
NS
N
SW
NE
EW
ESW
SW
N
NE
NESW
SW
W
NES
NS
S
NS
N
W
N
W
NS
N
NES
NE
EW
ESW
NEW
NESW
NESW
E
NSW
E
NES
NES
NE
E
W
NE
ESW
W
NESW
NEW
NESW
NW
W
NESW
ES
NESW
EW
NEW
E
NEW
S
S
S
ES
ES
NW
NEW
NS
NSW
S
NES
ESW
E
NESW
NW
NES
ES
NEW
NS
NEW
NES
NSW
NES
W
NS
SW
NSW
W
NS
N
NSW
N
NE
NEW
N
NE
NES
NES
N
NS
EW
NEW
NESW
NESW
NE
NES
EW
NES
ES
NES
S
NEW
NE
NS
ES
E
SW
NW
ESW
NESW
ESW
ESW
NESW
SW
NS
NES
NESW
NS
NW
NSW
ESW
NESW
ES
N
W
SW
EW
E
E
NE
N
E
W
NSW
S
NS
W
EW
NE
NE
SW
NES
NEW
NW
NEW
NE
W
EW
NEW
EW
NS
ES
NES
NE
NS
NSW
ESW
ES
NEW
NES
S
NESW
SW
W
NEW
S
ESW
NE
ES
E
NSW
NEW
SW
NEW
W
SW
N
EW
ESW
N
NW
NS
NESW
ES
NE
NES
ES
NS
N
N
NESW
NW
NES
S
E
E
ES
EW
NSW
N
NW
S
SW
SW
N
NE
EW
NES
EW
N
NE
NEW
W
NSW
NS
NES
NW
SW
S
NES
NESW
E
ESW
ES
NEW
NW
N
NES
ESW
S
NES
NW
NE
NEW
NES
E
W
ES
ES
NSW
NS
NES
ES
W
NE
S
S
SW
S
NE
NE
NS
NS
NES
W
NEW
NW
SW
NS
NW
NES
NW
NW
ESW
NSW
NESW
SW
NES
SW
NES
W
ESW
NW
N
NES
SW
ES
ES
EW
NEW
N
NS
ES
NEW
ES
S
NSW
NEW
NSW
ES
ESW
SW
N
NESW
NE
NESW
ES
SW
ES
N
NESW
NS
S
ES
NE
ES
ESW
N
NESW
NESW
N
ES
NW
NESW
NESW
W
NSW
ESW
W
ESW
EW
NE
NSW
N
W
NES
SW
ESW
NEW
NS
NESW
ES
E
NE
W
NW
N
NE
ESW
E
NS
ES
ESW
NESW
NE
E
W
ES
E
W
EW
EW
EW
NESW
W
ES
NW
N
ESW
E
ES
EW
ES
N
E
W
S
NS
EW
NESW
SW
NE
W
E
E
EW
W
NE
ES
NW
NES
NEW
N
ESW
N
NS
NES
N
E
NEW
ES
W
NW
NEW
NEW
E
EW
ESW
N
NSW
NW
ESW
NW
W
SW
ESW
ES
N
ESW
NEW
E
E
N
EW
W
SW
NW
NS
ESW
NES
SW
EW
W
NEW
S
NSW
SW
NEW
NSW
NEW
SW
NE
NSW
ESW
NES
NEW
E
NES
E
ES
NEW
ESW
ESW
E
NE
NEW
NES
SW
NS
W
NW
S
EW
SW
NESW
S
N
EW
EW
NEW
SW
S
NS
NS
E
NE
N
NES
EW
SW
SW
NES
ES
NES
NEW
NSW
W
NW
NS
N
SW
NS
S
NESW
W
NEW
NSW
NEW
NEW
NES
W
S
NSW
NEW
NSW
NEW
NSW
NES
NW
NE
N
ESW
W
NE
NW
NE
EW
NE
NS
E
ES
NS
E
NE
ESW
W
SW
NEW
NESW
EW
NS
S
E
EW
NW
NSW
NESW
NS
EW
EW
EW
W
N
ES
S
SW
N
NE
NS
E
S
E
NSW
SW
NS
NSW
NW
NEW
SW
S
ESW
NEW
S
NW
SW
SW
NESW
NS
E
W
NE
NES
NEW
E
NSW
NSW
EW
NES
NS
NE
ESW
ES
NW
NES
EW
S
W
NES
NEW
E
NEW
N
ES
E
N
EW
E
N
NEW
NEW
ESW
NE
ESW
N
ESW
ESW
N
ESW
N
EW
W
S
NES
NES
E
N
E
NSW
NESW
NE
W
EW
W
N
NEW
NESW
W
NS
W
S
N
NESW
N
NESW
NEW
S
NS
ES
EW
NSW
EW
NS
NESW
EW
NSW
NS
ES
ESW
N
NESW
NE
SW
E
NSW
S
S
W
S
EW
SW
NEW
NSW
W
E
E
ES
NW
ESW
W
NS
NE
E
NES
NSW
EW
ESW
NSW
NS
SW
NE
S
N
W
E
NW
SW
NESW
NSW
SW
NW
NESW
ES
NESW
ES
NE
NESW
N
NES
ESW
E
SW
W
NE
NW
ESW
SW
N
NSW
SW
SW
NEW
N
SW
NES
NEW
ESW
SW
W
SW
S
EW
S
NEW
NESW
NE
NES
NW
NS
NESW
NE
ESW
ES
N
NES
W
NW
N
EW
N
NES
NW
NESW
NEW
NE
EW
NSW
N
NEW
EW
W
NESW
NW
S
ESW
EW
ESW
NW
NSW
S
NSW
NE
NE
NW
NW
E
ES
S
NE
NES
NSW
S
ES
ESW
NW
NSW
S
NESW
E
NE
S
NS
ES
NS
S
SW
N
NE
N
NES
NES
NSW
NW
EW
W
SW
NESW
NES
SW
N
ESW
NES
NES
W
NW
ES
NS
NES
W
EW
NW
EW
NES
NES
EW
N
NE
NSW
NSW
S
E
NW
S
NEW
EW
N
NS
NW
NE
NS
EW
E
N
ES
S
EW
NES
NEW
W
NES
NESW
NW
NSW
NES
NW
NS
ESW
ES
NES
SW
EW
NE
NSW
NE
SW
EW
NSW
NS
NW
W
NEW
NW
S
ESW
NS
NES
EW
NW
W
S
NS
NES
E
ESW
N
NE
NES
SW
SW
NW
W
NW
W
ESW
ES
NEW
E
S
E
NE
ESW
NES
NEW
NW
S
NESW
SW
NS
NE
SW
EW
NW
W
S
SW
N
S
NS
ES
NES
NSW
NEW
E
N
NW
NSW
W
NEW
SW
NW
NESW
NS
ES
N
ES
EW
N
NES
SW
S
NS
ESW
N
EW
NEW
NW
NE
NW
NEW
ESW
NESW
NE
NESW
NW
NS
NE
S
W
NS
SW
N
EW
ES
NE
S
NE
NS
S
NSW
NESW
S
NSW
N
ES
N
S
NSW
W
NS
NS
NES
NE
NESW
NESW
S
NSW
ESW
NES
NS
ES
ESW
NS
ESW
N
W
E
SW
SW
NE
NE
E
NW
NE
ESW
ESW
NSW
W
NESW
NS
SW
N
NESW
SW
EW
W
E
W
NE
NSW
S
NES
N
E
NES
S
SW
W
ES
SW
NW
W
NE
NW
NEW
SW
N
W
ESW
NS
E
S
N
SW
NE
EW
S
NW
ESW
NES
NW
E
N
ESW
SW
ES
NSW
NEW
NS
ES
NE
NE
E
NE
S
S
NW
NEW
EW
EW
ESW
NESW
EW
E
E
NEW
W
NSW
NEW
W
W
NE
SW
NSW
S
ESW
E
NW
ESW
NESW
E
E
E
W
NS
E
ESW
NSW
S
ES
NW
NW
NSW
NSW
ESW
NS
E
NSW
N
S
ES
ESW
NE
W
NSW
ESW
ESW
NW
NES
EW
NS
ESW
NE
EW
W
ESW
S
E
EW
NEW
NW
S
NES
NEW
NW
ESW
NEW
NW
S
N
S
NS
NESW
NW
ESW
S
S
S
NES
NES
N
NE
W
SW
ES
S
NW
NE
S
NSW
NESW
NEW
NS
NS
NSW
W
NSW
NESW
E
EW
NEW
S
ESW
NES
NESW
NS
W
ES
NS
W
S
NSW
S
EW
NSW
SW
E
W
NW
SW
W
ES
ESW
NE
W
SW
EW
EW
S
N
NESW
N
NSW
ES
NS
NESW
NES
ESW
NE
NS
ESW
NW
NSW
ESW
N
ESW
E
NW
ESW
S
SW
S
NSW
W
NW
NSW
S
S
NESW
NES
S
NSW
NS
NW
NES
NW
NEW
ES
W
ES
NE
W
ES
ES
E
EW
EW
NW
ESW
NESW
S
ESW
NES
NES
W
NEW
ES
SW
EW
N
EW
ES
NEW
ESW
ES
NW
EW
NE
S
EW
EW
W
ESW
SW
NE
NES
W
NW
ESW
SW
NEW
SW
W
ESW
ESW
ESW
SW
NW
NES
SW
NSW
NS
NEW
S
S
ESW
NEW
ESW
NE
W
NESW
ESW
ES
EW
NSW
W
NES
ES
S
ESW
NW
EW
EW
NS
NW
ES
NEW
NS
N
NE
S
W
W
E
NEW
S
NESW
NS
ESW
NE
NE
W
NW
NW
ESW
E
NE
NS
NES
NESW
NES
ES
NE
NES
W
NESW
SW
NW
ESW
NW
E
SW
NE
ESW
E
NE
NW
NESW
NES
ESW
E
E
W
NSW
NEW
SW
SW
NEW
NE
ESW
W
NE
NEW
NEW
ESW
NS
NEW
NSW
EW
EW
W
NW
E
NS
S
NE
NW
NW
NSW
EW
EW
N
NW
EW
NESW
NEW
NSW
EW
SW
W
E
SW
NSW
NESW
NES
NES
N
NE
NEW
NSW
E
S
N
N
SW
NESW
SW
W
NSW
NW
S
NES
N
NW
NSW
ES
N
E
NESW
EW
S
NE
S
ESW
ESW
ESW
NEW
NES
NSW
NEW
NE
SW
SW
W
NEW
E
SW
E
ES
NEW
S
N
NES
N
NW
NEW
NES
S
NW
ES
NES
ESW
NSW
ESW
ESW
NESW
NW
EW
NW
N
EW
NESW
N
ESW
S
N
W
NESW
NW
NESW
ES
NS
N
NE
W
NES
NS
NW
NEW
SW
NEW
NES
W
N
W
NSW
SW
NS
ESW
E
NE
NESW
NES
NSW
ESW
ESW
NS
N
ES
NEW
NES
N
NS
NSW
ES
W
NEW
N
NSW
SW
W
NEW
W
EW
EW
S
ES
NESW
S
SW
S
NES
N
E
S
EW
NSW
NEW
NEW
E
NS
ES
SW
NSW
EW
NEW
E
ESW
ES
ES
NE
ESW
ES
NSW
NS
ESW
NE
NS
N
SW
NESW
W
NSW
S
W
W
NESW
NW
NES
NS
NEW
W
ES
S
EW
NW
NESW
NEW
NESW
NS
EW
EW
NES
NS
NW
NESW
NEW
NE
NE
NESW
E
NEW
NS
NSW
NSW
NEW
NE
ESW
SW
NSW
S
EW
S
NES
S
S
W
S
SW
NESW
ES
SW
NS
SW
NW
ES
ES
EW
ES
NSW
W
NEW
E
NES
NE
NE
SW
W
NS
ES
NW
W
W
NESW
NSW
NES
EW
NE
ES
NSW
SW
W
NEW
NEW
ES
SW
E
NSW
E
ESW
S
NE
NES
ESW
NS
NES
NSW
W
SW
ES
SW
SW
EW
NE
S
SW
NE
E
S
NES
ESW
ES
S
S
S
NEW
NS
N
NE
NE
NEW
EW
ES
EW
S
W
NW
S
NW
NSW
N
W
NS
SW
NEW
NSW
SW
NES
NSW
NESW
NS
NS
NW
ES
SW
NS
S
N
S
ES
E
NS
NEW
NEW
NEW
W
EW
SW
NW
NS
NE
N
SW
ES
W
NSW
E
SW
NW
E
ESW
NW
NW
E
NSW
ES
E
W
E
W
NES
ESW
NEW
S
NE
ESW
E
NS
E
S
ES
NE
W
NESW
NS
EW
NS
N
NS
NE
EW
NES
S
E
E
EW
EW
EW
NE
NW
W
NE
NE
NESW
ES
E
E
S
NSW
ESW
NES
SW
S
NW
E
EW
S
NSW
NEW
N
NE
NEW
NS
NE
NSW
NES
S
NES
NSW
ESW
W
W
ES
ES
NS
NEW
ES
NEW
NS
E
EW
ES
ESW
W
EW
E
NW
EW
SW
ES
NE
NEW
EW
N
N
NE
NEW
W
NE
NESW
NS
NE
N
EW
E
S
S
NW
EW
NS
NS
E
W
W
SW
E
SW
NW
NW
E
E
NE
NS
SW
EW
NE
NSW
ES
NE
NESW
NW
N
S
NS
N
E
EW
ES
N
NE
EW
NE
W
ESW
NS
NES
ES
W
NW
EW
NS
NESW
EW
E
NE
NW
EW
NSW
N
NSW
NEW
NE
ESW
NS
ES
W
NE
W
NEW
ESW
N
NEW
NSW
NES
E
NS
NES
NEW
W
S
ES
SW
S
N
ES
E
NSW
SW
NES
NSW
NE
NEW
NES
NS
N
ESW
NEW
EW
NW
ESW
E
N
NSW
NES
NES
SW
E
NW
S
W
NESW
NEW
NEW
NS
SW
ES
NEW
E
ES
ESW
W
EW
EW
NEW
NS
W
ESW
ES
W
ESW
E
NEW
N
S
NW
ES
NE
EW
ES
NSW
N
E
NES
NES
NW
ESW
NE
NS
EW
NEW
N
SW
N
ES
S
E
ESW
E
W
NW
NES
NES
NE
NE
NSW
NW
SW
ESW
ESW
ES
NSW
E
NE
SW
NW
N
E
NE
NSW
NES
W
NE
NS
NW
NEW
NS
N
NS
EW
NES
N
E
N
NSW
W
W
W
E
SW
W
N
ES
ESW
E
ESW
ESW
N
NSW
SW
NS
E
NE
S
NS
N
NW
NSW
W
SW
NESW
EW
NES
NS
SW
NES
W
SW
SW
NES
N
NSW
N
S
SW
N
NES
SW
NES
ESW
NSW
ES
NEW
S
EW
SW
NW
NSW
W
ESW
NEW
NE
E
NS
NS
W
NSW
N
E
NW
NSW
E
N
SW
NE
NES
E
NS
NE
SW
NEW
NE
NSW
E
NSW
ES
S
E
NSW
NES
NS
NEW
ES
NES
SW
ES
NSW
E
NSW
EW
E
S
NW
N
ESW
SW
ES
NES
NS
NSW
ES
NS
NS
NEW
W
ESW
NEW
E
SW
SW
ES
ES
NEW
NS
NE
NE
EW
ES
SW
NE
NS
EW
NEW
W
NSW
S
ES
NEW
NE
EW
S
N
NESW
SW
E
NEW
NW
NES
NEW
EW
NES
N
E
NEW
NES
NESW
EW
ES
EW
NE
ESW
NW
NES
ESW
S
NS
NW
NE
NS
NS
NEW
NESW
E
N
SW
ESW
EW
ESW
ES
ES
N
NW
ES
ES
NSW
NES
NS
NSW
N
ES
SW
SW
NEW
NEW
SW
NE
SW
EW
N
NS
E
W
W
NES
NW
NS
NEW
ESW
NE
NW
W
NES
NSW
NS
NESW
N
ESW
NS
SW
N
NW
ESW
SW
ES
W
NES
N
W
NES
ES
S
ESW
NESW
NE
ESW
ES
NES
NESW
N
NE
NEW
W
NE
NW
NE
NES
E
EW
E
NE
NESW
EW
N
W
E
W
NW
NS
NSW
EW
NW
S
NE
ES
S
NE
NEW
W
ESW
ESW
NESW
NES
NEW
N
NW
S
E
S
S
ES
NEW
W
NESW
NES
ESW
NE
NS
NS
NES
EW
NEW
N
ESW
EW
NW
NSW
NSW
NS
EW
S
NES
NSW
E
NSW
NW
NW
ES
SW
NES
NE
S
NES
NSW
NESW
NE
EW
NW
W
ES
NSW
N
NEW
EW
E
NEW
NSW
NESW
NEW
NE
NS
NS
SW
E
NEW
NEW
ES
N
ES
ESW
S
NES
S
NSW
NSW
NEW
ES
NEW
ES
N
NS
NW
EW
E
NES
NS
NES
N
NESW
W
NW
NE
NSW
W
S
ES
ESW
E
SW
W
N
N
W
EW
ESW
NSW
EW
E
NSW
NS
EW
SW
S
S
SW
NS
N
ESW
S
W
NE
NSW
E
W
ESW
S
N
NE
W
NESW
EW
NW
NE
EW
E
SW
NS
ESW
NW
NSW
SW
NE
NESW
ESW
NEW
NEW
S
NES
ES
NESW
E
NESW
S
NES
NS
NE
N
ES
N
ES
ESW
NEW
NW
ES
E
S
S
E
NES
NW
NS
ESW
NE
NESW
ESW
ESW
N
NW
NW
NW
NEW
NW
NESW
E
NE
NSW
E
NESW
NSW
N
NEW
ESW
N
ES
NE
NESW
SW
ES
S
NSW
EW
W
N
NE
ES
SW
NEW
NE
NE
NESW
NW
NSW
NEW
SW
SW
N
NEW
E
ESW
E
NEW
S
E
NW
E
NEW
EW
NESW
N
NESW
SW
NESW
ES
NESW
S
NSW
ES
NSW
N
ESW
NE
N
NEW
ES
N
SW
NESW
NW
N
NES
NEW
NS
NE
NES
NSW
ESW
S
NS
NE
NE
SW
NW
ES
S
NS
ES
ES
EW
E
NW
NES
N
NW
NE
NW
ES
NES
ESW
W
NEW
N
NE
N
NEW
ES
E
ESW
W
NSW
NW
N
N
ESW
NW
E
W
EW
NS
NW
NE
E
W
NEW
NES
SW
NE
EW
NEW
NS
W
S
SW
NEW
NEW
EW
EW
W
SW
S
SW
W
NESW
NEW
ESW
NS
SW
E
N
NEW
NEW
SW
ES
NE
N
S
NW
NSW
N
ESW
NEW
S
NEW
EW
NESW
NW
SW
ESW
NSW
NW
NEW
W
EW
NSW
NEW
NES
ES
NEW
NES
NE
W
NSW
NS
NS
NEW
SW
NW
N
ES
NESW
NW
NW
E
NW
NE
NE
ES
NS
S
W
ES
NES
NS
NSW
NW
E
W
ESW
NSW
NE
ES
NSW
NSW
NW
N
EW
NW
EW
NES
NSW
ESW
W
NS
NESW
NEW
N
ESW
ES
E
NW
S
E
NS
S
NSW
NSW
NESW
ES
NSW
E
ES
NS
EW
W
NS
E
NSW
E
NW
ES
W
ES
W
EW
NEW
E
NS
NES
W
ES
NW
NES
NW
ES
NEW
S
NS
ES
E
N
NEW
NEW
NS
ES
ES
NW
ESW
S
NES
NESW
ESW
NE
E
NE
ES
EW
NESW
E
N
NSW
EW
E
EW
E
ES
SW
ESW
NS
E
ES
NEW
SW
ESW
ESW
E
NESW
SW
NSW
EW
NES
NEW
E
NE
NW
EW
ES
W
NESW
NSW
NES
NESW
SW
W
S
NESW
N
NEW
W
NESW
E
NS
NESW
EW
EW
NW
NEW
SW
W
E
N
NEW
NES
EW
EW
SW
NEW
NESW
NE
N
NES
NESW
NS
NE
ESW
NEW
SW
W
NEW
NW
NE
E
NES
NW
E
NESW
E
NES
S
N
ES
E
ESW
SW
NES
W
EW
NW
EW
NSW
W
NS
NES
ES
S
NES
N
NW
ES
NES
E
NW
N
E
ESW
S
ESW
S
NESW
NSW
EW
ES
EW
ESW
EW
NE
EW
SW
NW
N
NEW
NS
EW
ES
NESW
NEW
ES
NS
W
N
E
NSW
W
S
N
NESW
E
NSW
NEW
ES
E
NW
NESW
E
S
E
S
NESW
E
NW
NSW
N
NES
E
NS
SW
EW
ESW
E
NS
E
W
W
S
EW
E
NES
NES
S
SW
EW
NESW
NSW
EW
ES
NE
ESW
NE
NW
W
W
SW
E
ESW
NW
E
ESW
NESW
N
ESW
ESW
NSW
N
NES
NW
S
N
ES
EW
EW
N
NES
SW
NW
E
W
NEW
EW
ES
E
NE
NES
NES
W
W
SW
S
NEW
EW
SW
ES
W
NSW
N
NES
ESW
NESW
NES
ESW
NE
NS
NS
NW
NES
NW
NS
EW
NE
E
NS
NSW
ES
NES
NESW
E
NW
ESW
NSW
N
NE
E
EW
NS
W
NES
W
NES
EW
NEW
S
NE
S
NSW
NE
SW
NEW
NES
E
NEW
NS
S
NSW
NES
NESW
ESW
SW
W
ESW
EW
ES
ESW
NES
E
NESW
ESW
E
ESW
SW
NEW
NSW
NE
EW
N
ESW
ESW
NE
S
NE
NESW
N
NES
NES
W
EW
NS
NE
EW
NESW
NE
NE
E
EW
NSW
NES
NW
SW
ESW
NEW
NSW
NES
EW
NE
EW
W
S
W
E
NS
NE
ES
SW
SW
E
NE
NEW
NS
NESW
ES
S
NSW
NSW
NEW
NSW
E
NS
NEW
ESW
ESW
NESW
NESW
ESW
NW
E
S
SW
NEW
NEW
NE
NEW
NSW
ESW
NS
NES
N
ESW
NEW
ESW
NW
N
NESW
SW
NW
NSW
NE
NE
NEW
ES
NES
E
NES
S
NW
NEW
NESW
EW
ES
N
ES
NES
W
W
NS
ESW
ESW
NE
NSW
W
S
NS
NW
NESW
W
ESW
EW
N
NEW
NS
NSW
EW
NE
NS
SW
NW
NEW
EW
ES
S
ES
NEW
SW
NES
NS
ES
ES
N
NS
N
NS
EW
EW
NESW
NESW
N
NE
S
ESW
N
NE
ES
E
W
N
NES
ESW
NE
N
NS
NSW
NW
NES
ES
NE
NEW
NSW
NSW
NSW
N
W
ES
NESW
NESW
ESW
NES
NSW
SW
NES
NEW
EW
NEW
S
SW
ES
NESW
N
S
NE
W
NES
N
NEW
NW
ES
NEW
NE
NES
NS
NW
NW
E
NW
E
S
W
SW
NW
S
ESW
NEW
NESW
ESW
SW
NSW
NES
N
NESW
E
NS
SW
EW
E
ES
NSW
NS
S
NS
S
E
EW
NSW
NESW
NSW
EW
E
ES
NESW
EW
ES
ES
EW
ES
ESW
ES
NES
NEW
W
NESW
ES
NESW
EW
EW
NW
NW
NESW
E
NESW
ESW
ES
NSW
NES
EW
NS
NEW
E
NW
EW
NEW
ESW
NW
S
NES
SW
SW
NW
N
NSW
NW
W
ESW
N
NEW
SW
EW
NS
EW
NS
W
W
NS
NW
NES
E
NEW
NE
ESW
S
NE
NSW
NES
EW
EW
ESW
NEW
NEW
E
NSW
N
SW
EW
EW
ES
ESW
E
N
NE
ES
N
NE
NSW
NW
N
S
ESW
NW
EW
NSW
NEW
NEW
ESW
N
NW
NESW
ESW
NES
NEW
NEW
SW
S
ESW
N
NSW
NESW
NE
NW
ES
NEW
NW
EW
NW
NES
NESW
ESW
NSW
NES
NE
NES
NSW
NSW
N
EW
SW
EW
NSW
EW
NW
EW
EW
ESW
NS
NEW
E
NW
NEW
NW
NS
EW
S
ESW
S
NE
SW
EW
ESW
S
W
W
NESW
NE
NSW
ESW
NW
NES
ES
E
NE
ES
E
NESW
NESW
EW
ESW
NS
NEW
SW
SW
W
NW
W
NES
NEW
ES
NEW
S
NS
E
SW
EW
ES
NEW
NE
N
NE
NS
NSW
NEW
NS
ES
W
NS
NW
E
S
NESW
NES
E
NS
E
ESW
W
NSW
NEW
NES
W
N
NS
ESW
NES
SW
S
NW
S
W
W
NS
NES
NES
N
S
NSW
N
E
SW
NSW
ESW
NESW
EW
NEW
NES
S
NW
NESW
ESW
NSW
S
ESW
NESW
NE
NES
N
SW
NESW
NS
N
NEW
NES
EW
W
NW
NSW
E
S
N
NES
NESW
E
NSW
ESW
ESW
ES
NEW
NSW
NSW
NS
NESW
S
NESW
EW
NW
E
S
NSW
NE
ESW
W
S
SW
NS
NE
SW
NW
NES
E
S
NW
NSW
NS
ES
EW
SW
S
E
E
EW
ESW
S
NSW
NES
NW
NES
SW
N
ES
NSW
E
NS
NE
NS
NS
SW
NW
NW
W
ES
ES
NEW
NESW
E
NE
NS
NSW
S
EW
NW
NSW
NES
W
E
EW
EW
SW
NS
ES
NW
EW
S
SW
NE
NES
ES
NSW
N
ESW
NSW
NS
S
ES
NES
SW
EW
ES
EW
ES
ES
ESW
E
N
W
S
W
NES
NW
NS
EW
S
NE
S
NES
N
NS
NESW
N
NESW
NESW
W
N
W
ES
SW
ESW
S
E
W
NESW
NW
N
NSW
NE
NESW
NS
E
S
SW
NESW
ES
ESW
SW
NE
NSW
NES
EW
NEW
ESW
S
ES
E
NSW
NEW
E
E
S
W
N
S
NES
W
W
ESW
NESW
NSW
ESW
N
W
W
NE
ES
NW
ESW
EW
NSW
NESW
NS
E
ESW
ESW
W
W
W
ESW
N
SW
NE
NW
ESW
ESW
NES
N
ESW
NW
NE
ES
NESW
NEW
NW
NS
NEW
EW
E
NE
NEW
NS
ESW
NSW
NESW
NW
ES
NW
N
NW
E
W
NS
NES
NW
W
SW
SW
NS
NES
NW
EW
NS
ESW
NEW
NW
S
EW
EW
ESW
NW
SW
E
N
NEW
SW
NS
W
W
NEW
S
EW
NE
SW
NE
NEW
ES
N
SW
SW
NESW
NSW
E
W
NW
NE
N
NE
N
NSW
ES
ES
NE
NE
NES
NESW
ESW
NS
SW
NS
W
W
NS
NE
S
S
NSW
NESW
NSW
ES
ESW
N
NW
N
NES
N
NES
NE
SW
NS
NE
S
E
E
NW
N
NSW
NEW
ESW
NEW
NE
ES
NW
NES
NW
E
NE
W
SW
NW
SW
NSW
EW
NW
W
SW
W
NS
W
NES
NESW
W
S
NE
EW
NSW
EW
EW
NW
W
N
NEW
NS
NW
NES
NES
ESW
NEW
ESW
NW
NEW
NESW
NEW
N
NES
SW
NESW
ES
NES
NW
NESW
W
NSW
N
NW
W
NEW
ESW
W
N
NS
NS
ES
NW
NSW
W
SW
NE
SW
NSW
ESW
ESW
NES
NEW
NW
S
E
ES
ES
NE
S
NE
E
NESW
NES
NE
NSW
NS
NSW
NES
S
E
NES
W
NES
NESW
W
SW
NSW
NESW
W
NESW
S
NSW
NSW
SW
NS
NEW
NESW
NEW
NE
NW
NSW
NS
NESW
NESW
EW
NS
NESW
EW
NEW
S
N
N
NESW
NES
NW
NS
SW
E
NS
NSW
ESW
S
ES
W
E
NE
NSW
NEW
EW
NW
NS
S
W
N
EW
NS
NSW
NES
E
NEW
SW
NE
SW
NW
NES
ESW
W
NESW
EW
NEW
NSW
E
ES
NS
NS
S
NESW
NW
ES
W
NSW
S
NE
EW
NS
NEW
NES
NEW
NES
NESW
E
N
ES
EW
NSW
NEW
SW
NEW
S
NSW
NESW
NEW
SW
ES
NESW
N
N
ES
NW
NEW
NESW
NSW
NEW
NES
ES
SW
NS
SW
ESW
NEW
W
SW
SW
W
W
NSW
SW
EW
ESW
ESW
NEW
NESW
NESW
S
NSW
NEW
S
NSW
NW
N
ESW
NE
W
S
ESW
NW
ES
NESW
W
NS
EW
ES
NEW
NW
ESW
N
ESW
NE
NS
W
NSW
ES
NESW
6 8
SW
NSW
ESW
NW
EW
NS
W
NEW
ES
ES
EW
NESW
S
NS
NEW
ES
NEW
NS
W
NESW
NS
NS
EW
NE
EW
E
SW
NW
ESW
S
S
ES
S
E
NE
ES
NW
NW
EW
S
NSW
NE
ES
NSW
ESW
ES
NW