Radio Contact

题目描述

农夫约翰丢失了他最喜欢的牛铃，奶牛贝茜同意帮助他寻找！他们沿着不同的路径在农场里分头搜索，但通过无线电保持联系，以便彼此保持沟通。不幸的是，他们的无线电电池电量所剩无几，因此他们希望规划移动方式以节省电量，尽量始终保持彼此之间的距离较短。

农夫约翰从位置 ($f_x, f_y$) 出发，计划沿一条由 $N$ 步组成的路径前进，每一步为 'N'（北）、'E'（东）、'S'（南）或 'W'（西）。贝茜从位置 ($b_x, b_y$) 出发，沿一条由 $M$ 步组成的类似路径前进。两条路径可能会经过相同的点。

在每一个时间步，农夫约翰可以选择停留在当前位置，或者沿着他的路径向前走一步（方向由路径中下一步决定，前提是他尚未到达路径的最终位置）。贝茜也可以做出类似的选择。在每一个时间步（不包括起始的第一步，即他们位于初始位置时），无线电消耗的能量等于他们之间距离的平方。

请帮助约翰和贝茜制定联合移动策略，使得从开始到并包括他们首次都到达各自路径终点的那个最终时间步为止，所消耗的总能量最小。

输入格式

第一行输入包含 $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$ 的正方向。

输出格式

输出一个整数，表示约翰和贝茜在旅途中可能消耗的最小能量。

2 7
3 0
5 0
NN
NWWWWWN

28

提示

题目来源：Brian Dean

标签: USACO|2016|Gold

来源

USACO|2016|Gold