在一个 的网格中,每个格子可能有人居住,也可能无人居住。行从上到下编号为 ,列从左到右编号为 。格点的坐标记为 ,其中 ,。
你需要输出一条从 到 、沿网格线移动的路径。每次移动可以到达上、下、左、右相邻的格点,但不能移出网格。
对于每个有人居住的格子,如果路径访问过构成该格子的四个顶点中的至少一个,则会在该格子产生 的费用。即使多次访问同一格子的顶点,该格子的费用也只计算一次。路径的费用为产生费用的格子数量。
具体评分方式请参见 Scoring 一节。
输入格式如下。
对于每个测试用例,输出以下两行。
是一个长度为 的字符串,其中每个字符均为 U、D、L、R 之一,分别表示从当前格点向上、向下、向左、向右移动一格。
所表示的移动必须从 开始,始终位于网格内,并最终到达 。
本题对每个子任务独立评分,以下近似比标准对所有子任务均相同。
设某个测试用例的最优费用为 ,选手输出的有效路径的实际费用为 。定义近似比 :
在第一个测试用例中,没有任何格子有人居住,因此所输出路径的费用为 。
在第二个测试用例中,左侧格子有人居住,而起点 是该格子的一个顶点,因此无论选择哪条路径,费用都至少为 。样例路径的费用为 。
在第三个测试用例中,虽然存在有人居住的格子,但所输出路径没有访问该格子的任何顶点。因此路径的费用为 。
每个测试用例的格式如下。
每个 都是长度为 的字符串,其中每个字符均为 0 或 1。
对于满足 、 的格子 ,如果 的第 个字符为 1,则该格子有人居住;如果为 0,则该格子无人居住。
必须与所输出路径的实际费用完全相等。此外,还必须满足
0 或 1。将一个子任务所包含的所有测试用例的 中的最大值记为该子任务的 。该子任务获得下列条件中能够满足的最高得分比例。
条件 | 得分比例 |
|---|---|
对所有测试用例均有 | |
其他情况 |
在倒数第二项条件中,、、 均指同一个测试用例中的值。最终得分为四个子任务所得分数之和。
如果输出的路径无效,或同时输出的费用与路径的实际费用不同,则该提交的得分为 分。
| 3 | 15 | 附加条件:每个测试用例均满足 。 |
| 4 | 65 | 附加条件:每个测试用例均满足 。 |
在第四个测试用例中,最优费用为 ,而所输出路径的费用为 。因此该测试用例的近似比为
样例输入中所有测试用例的近似比均不超过 ,因此该样例输出在所有子任务中均满足最高得分比例的条件。