← 返回题目列表

AtCoder · icpc2013summer_day4_b

B. 被踩过的电缆

中文机器翻译题面 查看原题

问题陈述

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