题解

#include <bits/stdc++.h> 
using namespace std;

using ll = long long;

using vi = vector<int>;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair

int N, M;

const int INF = 1e9 + 7;
const int MX = 1e3 + 1;

int sq(int a) { return a * a; }

int dist(pi a, pi b) {  
	return sq(a.f - b.f) + sq(a.s - b.s);
}

map<char, int> md{{'N', 0}, {'E', 1}, {'S', 2}, {'W', 3}};

const int dx[4]{0, 1, 0, -1};
const int dy[4]{1, 0, -1, 0};
int dp[MX][MX];

int main() {
	cin >> N >> M;

	vector<pi> jl(N + 1); 
	vector<pi> bl(M + 1);  

	int a, b;
	cin >> a >> b;

	jl[0] = {a, b};
	cin >> a >> b;
	bl[0] = {a, b}; 

	string jS, bS;  
	cin >> jS >> bS;
	for (int i = 0; i < sz(jS); i++) {
		jl[i + 1] = {jl[i].f + dx[md[jS[i]]], jl[i].s + dy[md[jS[i]]]};
	}

	for (int i = 0; i < sz(bS); i++) {
		bl[i + 1] = {bl[i].f + dx[md[bS[i]]], bl[i].s + dy[md[bS[i]]]};
	}
	fill_n(dp[0], MX * MX, INF);

	dp[0][0] = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + dist(jl[i + 1], bl[j]));
			dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + dist(jl[i], bl[j + 1]));
			dp[i + 1][j + 1] =
			    min(dp[i + 1][j + 1], dp[i][j] + dist(jl[i + 1], bl[j + 1]));
		}
	}

	cout << dp[N][M] << "\n";
}