20ptWA+TLE

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int n, m;
const int N = 1005;
string s1, s2;
int dirf[N], dirb[N];
int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0};
ll dp[N][N];
ll dis(int p1, int p2, int k1, int k2){
	return ((p1-k1) * (p1-k1)) + ((p2-k2) * (p2-k2));
}
ll dfs(int fx, int fy, int bx, int by, int pos1, int pos2){
	if(pos1 > n || pos2 > m)
		return dp[pos1][pos2];
	if(pos2 == m && pos1 == n){
		return dis(fx, fy, bx, by);
	}	
//	cout << dp[pos1][pos2] << "\n";
	int nfx = dx[dirf[pos1]] + fx;
	int nfy = dy[dirf[pos1]] + fy;
	int nbx = dx[dirb[pos2]] + bx;
	int nby = dy[dirb[pos2]] + by;
//	cout << nfx << " " << nfy << " " << nbx << " " << nby << "\n"; 
	dp[pos1][pos2] = min(dfs(fx, fy, nbx, nby, pos1, pos2+1)+dis(fx, fy, nbx, nby), dp[pos1][pos2]);
	dp[pos1][pos2] = min(dfs(nfx, nfy, bx, by, pos1+1, pos2)+dis(nfx, nfy, bx, by), dp[pos1][pos2]);
	dp[pos1][pos2] = min(dfs(nfx, nfy, nbx, nby, pos1+1, pos2+1)+dis(nfx, nfy, nbx, nby), dp[pos1][pos2]); 
	return dp[pos1][pos2];
}
int main(){
	cin >> n >> m;
	int fx, fy, bx, by;
	cin >> fx >> fy >> bx >> by >> s1 >> s2;
	for(int i = 1; i <= n; i++){
		if(s1[i-1] == 'N')
			dirf[i] = 0;
		if(s1[i-1] == 'S')
			dirf[i] = 1;
		if(s1[i-1] == 'W')
			dirf[i] = 2;
		if(s1[i-1] == 'E')
			dirf[i] = 3;
	}
	for(int i = 1; i <= m; i++){
		if(s2[i-1] == 'N')
			dirb[i] = 0;
		if(s2[i-1] == 'S')
			dirb[i] = 1;
		if(s2[i-1] == 'W')
			dirb[i] = 2;
		if(s2[i-1] == 'E')
			dirb[i] = 3;
	}
	memset(dp, 0x3f, sizeof dp);
	//dp[0][1] = dp[1][0] = 0;
	dfs(fx, fy, bx, by, 1, 1);
	cout << dp[1][1];
	return 0;
}