#include<bits/stdc++.h>
using namespace std;
int dp[55][55][4];
int mp[55][55];
int tx,ty;
int n,m;
void dfs(int x,int y,int cost,int c){
	if(cost>=dp[x][y][c])return;
	
	dp[x][y][c]=cost;
	
	if(x==tx&&y==ty)return;
	
	int tcost;
	if(c==0)tcost=0;
	else if(c==3)tcost=2;
	else tcost=1;
	
	if(x-1>0&&mp[x-1][y]==0&&mp[x-1][y+1]==0){
		dfs(x-1,y,cost+1+tcost,0);
		if(x-2>0&&mp[x-2][y]==0&&mp[x-2][y+1]==0){
			dfs(x-2,y,cost+1+tcost,0);
			if(x-3>0&&mp[x-3][y]==0&&mp[x-3][y+1]==0){
				dfs(x-3,y,cost+1+tcost,0);
			}
		}
	}//up 
	
	
	if(c==3)tcost=0;
	else if(c==0)tcost=2;
	else tcost=1;
	
	if(x+1<n&&mp[x+2][y]==0&&mp[x+2][y+1]==0){
		dfs(x+1,y,cost+1+tcost,3);
		if(x+2<n&&mp[x+3][y]==0&&mp[x+3][y+1]==0){
			dfs(x+2,y,cost+1+tcost,3);
			if(x+3<n&&mp[x+4][y]==0&&mp[x+4][y+1]==0){
				dfs(x+3,y,cost+1+tcost,3);
			}
		}
	}//down
	
	if(c==2)tcost=0;
	else if(c==1)tcost=2;
	else tcost=1;
	
	if(y-1>0&&mp[x][y-1]==0&&mp[x+1][y-1]==0){
		dfs(x,y-1,cost+1+tcost,2);
		if(y-2>0&&mp[x][y-2]==0&&mp[x+1][y-2]==0){
			dfs(x,y-2,cost+1+tcost,2);
			if(y-3>0&&mp[x][y-3]==0&&mp[x+1][y-3]==0){
				dfs(x,y-3,cost+1+tcost,2);
			}
		}
	}//left
	
	if(c==1)tcost=0;
	else if(c==2)tcost=2;
	else tcost=1;
	
	if(y+1<m&&mp[x][y+2]==0&&mp[x+1][y+2]==0){
		dfs(x,y+1,cost+1+tcost,1);
		if(y+2<m&&mp[x][y+3]==0&&mp[x+1][y+3]==0){
			dfs(x,y+2,cost+1+tcost,1);
			if(y+3<m&&mp[x][y+4]==0&&mp[x+1][y+4]==0){
				dfs(x,y+3,cost+1+tcost,1);
			}
		}
	}//left
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>mp[i][j];
	int sx,sy;
	cin>>sx>>sy;
	if(sx>=n||sy>=m||mp[sx][sy]||mp[sx+1][sy]||mp[sx][sy+1]||mp[sx+1][sy+1]){
		cout<<"-1";
		return 0;
	}
	cin>>tx>>ty;
	if(tx>=n||ty>=m||mp[tx][ty]||mp[tx+1][ty]||mp[tx][ty+1]||mp[tx+1][ty+1]){
		cout<<"-1";
		return 0;
	}
	char s;
	cin>>s;
	
	int to;
	if(s=='N')to=0;
	else if(s=='S')to=3;
	else if(s=='E')to=1;
	else to=2;
	memset(dp,0x3f,sizeof(dp));
	dfs(sx,sy,0,to);
	if(dp[tx][ty][0]==0x3f3f3f3f&&dp[tx][ty][1]==0x3f3f3f3f&&dp[tx][ty][2]==0x3f3f3f3f&&dp[tx][ty][3]==0x3f3f3f3f)cout<<"-1"<<endl;
	else cout<<min(min(dp[tx][ty][0],dp[tx][ty][1]),min(dp[tx][ty][2],dp[tx][ty][3]))<<endl;
	return 0;
} 

非常平平无奇但它在#9 TLE了

能确定不是死递归

大佬们能帮忙优化一下吗