問題文
N × N 在格子中,M 台机器人,B 个方块,1 个目标格。
每个格子都有坐标,左上角格子的坐标是 (0, 0),右上角格子的坐标是 (0, N - 1),右下角格子的坐标是 (N - 1, N - 1) 。该格子的左端和右端、上端和下端分别相连,例如格子 (3, 0) 的左邻格是 (3, N - 1)、马斯 (N - 1, 5) 的正下方格是 (0, 5) 。
各罗博托 i (1 \leq i \leq M) 关于,源 (ry_i, rx_i) 与方向的少年值 c_i 。c_i 是
仅由 U, D, L, R 是其中之一,分别表示上下左右。
另外,还会给出每个方块格子和目标格的坐标。i 第几个方块格(1 \leq i \leq B)的坐标是 (by_i, bx_i),目标格的坐标是 (gy, gx) 。
你可以选择若干个格子,并在它们上面设定 方向案内 ,每个方向指示都需要指定上下左右的一个方向。1 无法在一个格子上设置多个方向指示。
方向指示设置完成后,每个机器人会各自重复以下动作。机器人之间不会发生冲突。
- 当位于目标格时:在该位置停止。
- 在非这种情况下:首先,如果当前所在的格子上设置了方向指示,就将自己的朝向改为指定的方向。随后,向自己朝向的方向 1 移动格子(注意格子的左端与右端、上端与下端是相连的)。但是,如果移动到的格子是块格子,则移动失败,并停留在原地。
请尽可能让能够在有限次数动作内到达目标格子的机器人数量增加。使用的方向指示越少,机器人经过的格子越多,将获得更高的分数。详细情况请确认“输出”部分。
【注意】在本问题中,不需要求“最优解”。例如,不必让所有机器人都到达目标,也不必将方向指示数量最小化。
制約
- N = 40
- M = 100
- B = 300
- 0 ≦ gy, gx ≦ N - 1
- 0 ≦ ry_i, rx_i ≦ N - 1
- c_i 是
仅由
U,D,L,R为其中之一。 - 0 ≦ by_i, bx_i ≦ N - 1
- 方块格子不会与机器人、目标格子或其他方块格子重叠。(机器人之间或机器人与目标格子之间有时可能重叠)
- 在满足以上否定条件的范围内,方块格子、目标格子、机器人所在的格子都是均匀随机选取的存在。
入力
输入采用以下格式给出。
N M B gy gx ry_1 rx_1 c_1 ry_2 rx_2 c_2 : ry_M rx_M c_M by_1 bx_1 by_2 bx_2 : by_B bx_B
出力
设置的方向指示的数量 K、i 设置第几个方向指示的坐标 (Y_i, X_i)、i 指定给第几个方向指示的方向 R_i (U, D, L, R 是上述任意一项,对应上下左右,按以下格式输出。
K
Y_{1} X_{1} R_1
Y_{2} X_{2} R_2
:
Y_{K} X_{K} R_K
如果不满足上述格式,有时会判定为“不正确”。例如,字符串数量不匹配或使用了指定以外的字符。
此外,即便在同一格子上设置多个方向指示,也会判定为不正确。但在目标格子或方块格子上设置方向指示不会判定为不正确。
测试用例 50 将给定的个数。对于每个测试用例,能够在有限次数的动作中到达目标的机器人数量为 A,设置的方向指示数量为 B,机器人即便短暂经过的格子数量为 C ,则该测试用例中 1000 \times A - 10 \times B + C 点将被取得。全部测试用例的总分为该提交的得分。
如果产生了不正确的输出,并且该测试用例属于给定的输入示例,则该测试用例的得分为 0 点。对于其他测试用例,输入示例之外的所有测试用例的得分为 0 点。
入出力例
输入示例和输出示例可以 从该库 下载。