如题。小数据拍了半个小时没结果 大数据一分钟出来，也没看出来什么性质

#include<bits/stdc++.h>
#define int long long
#define N 2000010 
#define CQD 1000
#define MOD 1000000007
#define DEBUG(x) (cout<<#x"="<<x<<'\n')
#define lowbit(a) ((a)&(-(a)))
using namespace std;
int m,n,lnsz,hd[N],dijk[N];
char mp[300][300];bool vis[N];
bool isha(char c){
	return c>='A'&&c<='Z';
}
struct ln{
	int u,v,w,nxt;
}a[N<<2];
void mrg(int u,int v,int w){
	a[++lnsz].u=u;
	a[lnsz].v=v;
	a[lnsz].w=w;
	a[lnsz].nxt=hd[u];
	hd[u]=lnsz;
//	cout<<"Mrg:("<<u/(n+1)<<","<<u%(n+1)<<")->("<<v/(n+1)<<","<<v%(n+1)<<"),w="<<w<<endl;
}
struct cmp{
	bool operator () (int a,int b){
		return dijk[a]>dijk[b];
	}
};
priority_queue<int,vector<int>,cmp> q;
void dij(int root){
	dijk[root]=0;vis[root]=1;
	q.push(root);
	while(!q.empty()){
		int tp=q.top();q.pop();vis[tp]=0;
		for(int i=hd[tp];i;i=a[i].nxt)
			if(dijk[a[i].v]>dijk[tp]+a[i].w){
				dijk[a[i].v]=dijk[tp]+a[i].w;
				if(!vis[a[i].v]){
					vis[a[i].v]=1;
					q.push(a[i].v);
				}
			}
	}
}
int arqd(char a,char b){
	int ans=0;
	while(a!=b){
		ans++;
		if(a=='N')a='E';
		else if(a=='E')a='S';
		else if(a=='S')a='W';
		else a='N';
	}
	return ans;
}
signed main(){
	freopen("explore.in","r",stdin);
	freopen("explore.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie();cout.tie();
	cin>>m>>n;
	for(int i=0;i<N;i++)dijk[i]=9220000000000000000ll;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			cin>>mp[i][j];
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++){
			if(mp[i][j]=='X')continue;
			if(i!=1)mrg(i*CQD+j,(i-1)*CQD+j,arqd(mp[i][j],'N'));
			if(j!=1)mrg(i*CQD+j,i*CQD+j-1,arqd(mp[i][j],'W'));
			if(i!=m)mrg(i*CQD+j,(i+1)*CQD+j,arqd(mp[i][j],'S'));
			if(j!=n)mrg(i*CQD+j,i*CQD+j+1,arqd(mp[i][j],'E'));
		}
	memset(vis,0,sizeof(vis));
	dij(CQD+1);
	if(dijk[m*CQD+n]==9220000000000000000ll)dijk[m*CQD+n]=-1;
	cout<<dijk[m*CQD+n]<<endl;
	return 0;
}