레이팅 미적용농부 존이 가장 아끼는 소 방울을 잃어버렸고, 젖소 베시가 찾는 것을 돕기로 했다! 둘은 서로 다른 경로를 따라 흩어져 농장을 수색하되, 무전기로 계속 연락을 주고받는다. 안타깝게도 무전기의 배터리가 얼마 남지 않아서, 항상 서로 가까운 거리를 유지하도록 이동 계획을 세워 전력을 아끼려 한다.
농부 존은 위치 (\(f_x, f_y\))에서 출발하여 \(N\)개의 걸음으로 이루어진 경로를 따라갈 계획인데, 각 걸음은 'N'(북), 'E'(동), 'S'(남), 'W'(서) 중 하나이다. 베시는 위치 (\(b_x, b_y\))에서 출발하여 \(M\)개의 걸음으로 이루어진 비슷한 경로를 따라간다. 두 경로는 공통 지점을 지날 수도 있다. 각 시간 단계마다 농부 존은 현재 위치에 머무르거나, 자기 경로에서 다음으로 정해진 방향으로 한 걸음 나아갈 수 있다 (아직 경로의 마지막 위치에 도달하지 않았다면). 베시도 같은 선택을 할 수 있다. 각 시간 단계마다 (초기 위치에서 시작하는 첫 단계는 제외) 무전기는 두 사람 사이 거리의 제곱만큼의 에너지를 소모한다.
둘 다 각자 경로의 마지막 위치에 처음 도달하는 마지막 단계까지 포함하여, 소모되는 총 에너지를 최소화하는 공동 이동 전략을 세우도록 농부 존과 베시를 도와주자.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(N\)과 \(M\) (\(1 \leq N, M \leq 1000\))이 주어진다. 둘째 줄에 정수 \(f_x\)와 \(f_y\)가, 셋째 줄에 \(b_x\)와 \(b_y\)가 주어진다 (\(0 \leq f_x, f_y, b_x, b_y \leq 1000\)). 다음 줄에 농부 존의 경로를 나타내는 길이 \(N\)의 문자열이, 마지막 줄에 베시의 경로를 나타내는 길이 \(M\)의 문자열이 주어진다.
농부 존과 베시의 좌표는 이동 내내 항상 범위 (\(0 \leq x,y \leq 1000\)) 안에 있음이 보장된다. 동쪽은 x 양의 방향, 북쪽은 y 양의 방향임에 유의하자.
농부 존과 베시가 이동하는 동안 사용할 수 있는 최소 에너지를 하나의 정수로 출력한다.
radio.in · 출력을 쓸 파일 radio.out2 7
3 0
5 0
NN
NWWWWWN28