问题陈述
Nathan O. Davis 正在经营一家公司。 他的公司拥有一个拥有大量用户的网络服务。所以他的办公室里充满了服务器、路由器和凌乱的局域网电缆。
他现在对那些乱七八糟的电缆感到非常困惑,因为它们引发了各种各样的问题。 例如,在公司工作的员工经常被电缆绊倒。 如果电缆断开,不会造成任何损坏。这只是幸运而已。 如果连接电缆,计算机可能会掉落并损坏。 他即将推出一台新计算机和一条新电缆。 他希望尽量减少员工在新电缆上行走的次数。
他的办公室布置在二维网格中, H \times W 细胞。 新电缆应沿着电池的边缘编织。 电缆的每一端都位于单元的一角。 网格以零原点坐标表示,其中左上角为(0, 0)。
每个工作人员都从某个单元格内开始工作,每天以固定的重复模式沿着网格在办公室内行走。
步行模式由四个字符组成的字符串描述 U, D, L 和 R.
U 表示向上移动, D 表示向下移动, R 表示向右移动,并且 L 表示向左移动。
例如, UULLDDRR 表示依次向上、上、左、左、下、下、右、右移动。
工作人员重复固定的模式 T 次。请注意,如果工作人员要穿过墙壁离开网格,则工作人员会留在牢房中。
你有所有工作人员的移动模式和新电缆两端的位置。 您的工作是找到新电缆的最佳放置位置,从而最大限度地减少员工跨过电缆的总数。
输入
输入的第一行包含三个整数,代表办公室的尺寸 W, H (1 \leq W, H \leq 500),以及员工人数 N (1 \leq N \leq 1000),分别。 下一行包含两个 x-y 对 (0 \leq x \leq W, 0 \leq y \leq H),表示要连接的网线两个端点的位置。 这些值表示电缆左上角所插入的单元格的坐标。 例外的是, x = W 表示最右边单元格的右边缘,并且 y = H 表示最底部单元格的底部边缘。
以下几行描述了员工的初始位置及其移动模式。
第一行包括一个 x-y 对 (0 \leq x \lt W, 0 \leq y \lt H),它表示人员初始单元格的坐标。
下一行有一个整数 T (1 \leq T \leq 100)和一个字符串,其中包含 U, D, L 和 R,其含义如上所述。
模式字符串的长度大于或等于 1,且不超过 1,000。
这两行重复 N 次。
输出
输出他的员工在单行中跨过电缆的最少次数。
示例输入 1
3 3 1 1 1 3 3 0 0 1 RRDDLLUU
样本输入 1 的输出
1
示例输入 2
3 3 1 0 0 3 3 0 0 1 RRDDLLUU
样本输入 2 的输出
0
示例输入 3
3 3 1 1 1 3 3 0 0 10 RRDDLLUU
样本输入 3 的输出
10
示例输入 4
3 3 4 1 1 3 3 0 0 10 R 2 0 10 D 2 2 10 L 0 2 10 U
样本输入 4 的输出
1