Radio Contact

// CodeSnip{CPP Short Template}
 
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) {  // distancia al cuadrado entre dos puntos
	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};
 
// i = paso actual de John
// j = paso actual de Bessie
 
int dp[MX][MX];
 
int main() {
	setIO("radio");
 
	cin >> N >> M;
 
	vector<pi> jl(N + 1);  // ubicación de john
	vector<pi> bl(M + 1);  // ubicación de bessie
 
	int a, b;
	cin >> a >> b;
 
	jl[0] = {a, b};  // ubicación inicial de john
	cin >> a >> b;
	bl[0] = {a, b};  // ubicación inicial de bessie
 
	string jS, bS;  // strings de movimiento de john y bessie
	cin >> jS >> bS;
 
	// calcular los movimientos de ambos
	// dx[md[jS[i]]] puede parecer complicado, pero solo mapea el carácter a su
	// cambio
 
	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]]]};
	}
 
	// o se mueve john, o se mueve bessie, o se mueven ambos
 
	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";
}

import java.io.*;
import java.util.*;
 
public class radio {
	public static int[][] fjLocs;
	public static int[][] bLocs;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("radio.in"));
		PrintWriter pw = new PrintWriter(new FileWriter("radio.out"));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
 
		fjLocs = new int[N + 1][2];  // Ubicaciones de FJ.
		bLocs = new int[M + 1][2];   // Ubicaciones de Bessie.
 
		// Ubicación original de FJ.
		st = new StringTokenizer(br.readLine());
		fjLocs[0][0] = Integer.parseInt(st.nextToken());
		fjLocs[0][1] = Integer.parseInt(st.nextToken());
 
		// Ubicación original de Bessie.
		st = new StringTokenizer(br.readLine());
		bLocs[0][0] = Integer.parseInt(st.nextToken());
		bLocs[0][1] = Integer.parseInt(st.nextToken());
 
		// Encontrar las ubicaciones que visitan ambos.
		String fjPath = br.readLine();
		String bPath = br.readLine();
		fill(fjLocs, fjPath);
		fill(bLocs, bPath);
 
		/*
		 * dp[i][j] es el costo mínimo para que
		 * FJ dé i pasos, y para que Bessie dé j pasos.
		 */
		int[][] dp = new int[N + 1][M + 1];
 
		// Si FJ se mueve, y Bessie se queda quieta.
		for (int i = 1; i <= N; i++) {
			dp[i][0] = dp[i - 1][0] + cost(fjLocs[i], bLocs[0]);
		}
 
		// Si FJ se queda quieto, y Bessie se mueve.
		for (int j = 1; j <= M; j++) {
			dp[0][j] = dp[0][j - 1] + cost(fjLocs[0], bLocs[j]);
		}
 
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				// El costo actual en esta celda.
				int curCost = cost(fjLocs[i], bLocs[j]);
				// Calcular distintos costos según quién se mueve.
				int bothMove = dp[i - 1][j - 1] + curCost;
				int fjMove = dp[i - 1][j] + curCost;
				int bMove = dp[i][j - 1] + curCost;
				dp[i][j] = Math.min(Math.min(bothMove, fjMove), bMove);
			}
		}
 
		pw.println(dp[N][M]);
		pw.close();
	}
 
	// Llenar los arreglos de ubicación de FJ y Bessie.
	public static void fill(int[][] loc, String dir) {
		for (int i = 1; i <= dir.length(); i++) {
			loc[i][0] = loc[i - 1][0];
			loc[i][1] = loc[i - 1][1];
 
			// Cambio de ubicación según la dirección.
			char c = dir.charAt(i - 1);
			if (c == 'N') { loc[i][1]++; }
			if (c == 'E') { loc[i][0]++; }
			if (c == 'S') { loc[i][1]--; }
			if (c == 'W') { loc[i][0]--; }
		}
	}
 
	// Cuadrado de la distancia entre los puntos a y b.
	public static int cost(int[] a, int[] b) {
		return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);
	}
}