1 #include <bits/stdc++.h> 
 2 #define For(i,j,k) for(int i=j;i<=k;i++)
 3 using namespace std ; 
 4 
 5 const int dx[4] = { 0,1,0,-1 } ; 
 6 const int dy[4] = { 1,0,-1,0 } ; 
 7 const int N = 61 ; 
 8 int n,m,sx,sy,tx,ty,dir,tmp ; 
 9 int a[N][N] ; 
10 char s[3] ; 
11 struct node{
12     int x,y,dir,step ; 
13 };
14 queue<node> Q ; 
15 bool visit[51][51][4] ; 
16 bool flag ; 
17 
18 inline void impossible() 
19 {
20     printf("-1\n") ; 
21     exit(0) ; 
22 }
23 
24 inline void bfs(int x,int y,int dir) 
25 {
26     node p,q ; 
27     p.x = x; p.y = y ; p.dir = dir ; p.step = 0 ; 
28     Q.push(p) ;
29     visit[ p.x ][p.y][p.dir] = 1 ;  
30     while(!Q.empty()) {
31         p = Q.front() ; 
32         Q.pop() ; 
33         For(i,1,5) {
34             q = p ; q.step++ ; 
35             bool flag = 0 ; 
36             if(i<=3) {
37                 For(j,1,i) {   //要注意的是要把这几步中的都验证一遍 
38                             //防止出现跳跃障碍物的情况 
39                     q.x+=dx[ q.dir ] ; 
40                     q.y+=dy[ q.dir ] ; 
41                     if(a[q.x][q.y]) flag = 1 ; 
42                 }
43             }
44             else {
45                 if(i==4) q.dir = (q.dir+1)%4 ; 
46                 else     q.dir = ((q.dir-1)%4+4)%4 ; 
47             } 
48             if(flag) continue ; 
49             if(visit[ q.x ][q.y][q.dir]) continue ; 
50             if(a[q.x][q.y]) continue ; 
51             if(!(q.x>=1&&q.x < n&&q.y>=1&&q.y < m) ) continue ;  
52             visit[ q.x ][q.y][q.dir] = 1 ; 
53             
54             Q.push(q) ; 
55             if(q.x==tx&&q.y==ty) {
56                 printf("%d\n",q.step) ;  
57                 exit(0) ; 
58             }
59         }
60     }
61 }
62 
63 int main() 
64 {
65     scanf("%d%d",&n,&m) ; 
66     For(i,1,n) 
67         For(j,1,m) {
68             scanf("%d",&a[ i ][ j ]) ; 
69             if(a[i][j]) a[i-1][j] = a[i][j-1] = a[i-1][j-1] = 1 ; 
70         }
71     For(i,1,n) a[i][m] = 1 ; 
72     For(i,1,m) a[n][i] = 1 ; 
73     scanf("%d%d%d%d%s",&sx,&sy,&tx,&ty,s) ; 
74     if(a[sx][sy]) 
75         impossible() ; 
76     if(sx==tx&&sy==ty) {       //   特判  起点与终点重合   
77         printf("0\n") ; 
78         exit(0) ; 
79     }    
80     if(s[0]==‘E‘) dir = 0 ;
81     if(s[0]==‘S‘) dir = 1 ;
82     if(s[0]==‘W‘) dir = 2 ;
83     if(s[0]==‘N‘) dir = 3 ; 
84     bfs(sx,sy,dir) ; 
85     printf("-1") ;   //  如果一直没有终止  说明没到终点，无法到达  输出  -1      
86     return 0 ; 
87 }