AT_pakencamp_2018_day2_h プレゼント配り　(Santa Claus' Track)

PAKEN CITY 以一个 $(2N+1) \times (2N+1)$ 的网格来表示。每个格子通过其坐标 $(i, j)$ 表示，其中 $i$ 为「行号」，$j$ 为「列号」。格子有三种类型：「道路」、「空地」和「房屋」。行号和列号中至少有一个为偶数的格子为道路，两个都是奇数的格子可能是空地或房屋。输入中的 $S_{R, C}$ 对应于格子 $(2R+1, 2C+1)$，其中 `.` 表示空地，`1` 到 `9` 表示房屋，数字表示住在房屋中的人数。 圣诞老人的小帮手 reiji1112 将从一个道路交叉口（行号和列号均为偶数的格子）开始移动，要求路线不重复经过同一格，且经过 $K$ 个或更少的交叉口后返回起点。移动过程中，靠近房屋（四个正交方向相邻）的地方可以向房屋分发礼物。每个房屋最多可以收到等于住户人数的礼物，并且不能重复给同一个房屋分配礼物。 请为圣诞老人设计一条路径，使他能分发尽可能多的礼物。 下面是一个例子与其对应的圣诞老人移动路径： ``` 3 6 123 4.5 678 ``` 在这种情况下，圣诞老人可以向 $2 + 4 + 5 + 6 + 7 + 8 = 32$ 人分发礼物。

第一行输入两个整数 $N$ 和 $K$，接下来的 $N$ 行每行是一串字符，表示网格中的房屋和空地。

需要输出圣诞老人的移动路径。具体来说，起点坐标为 $(2R, 2C)$，从起点依次向东、西、南、北移动 2 格，分别用 `R`, `L`, `D`, `U` 表示，最终组成一个不超过 $K$ 字符的字符串 $X$。对于每个测试用例，需输出： > $R$ $C$ $X$ 其中 $X$ 的长度需不超过 $K$。例如，前述图中的输出为 `1 1 DDRUUL`。如果无法找到符合要求的路径，则输出： > $-1$ $-1$ $-1$ 需要为总共 6 个测试用例输出 6 行结果。注意，请确保路径始终能回归至起点，且不会超过 PAKEN CITY 的范围，否则将导致错误。

### 测试用例 测试用例的信息如下： | 测试用例编号 | 总分 | $N$ | $K$ | $V_1$ | $V_2$ | $V_3$ | $V_4$ | $V_5$ | |--------------|------|-----|-----|-------|-------|-------|-------|-------| | #1 | 10 | 9 | 24 | 220 | 260 | 271 | - | - | | #2 | 18 | 100 | 280 | 2766 | 2937 | 3051 | 3110 | 3230 | | #3 | 18 | 500 | 1400| 13299 | 14104 | 14641 | 14940 | 15820 | | #4 | 18 | 500 | 1400| 3346 | 3975 | 4394 | 4600 | 5060 | | #5 | 18 | 500 | 1400| 11368 | 15543 | 16198 | 16600 | 17490 | | #6 | 18 | 100 | 1000| 8950 | 9783 | 10338 | 10660 | 11310 | 输入数据可以通过下载提供的 [ZIP 文件](https://goo.gl/M3m7fH) 获取。 ### 得分计算 得分系统如下： - $V_1$ 是 25 分界线。得分低于其 0.8 倍时为 0 分，介于 0.8 倍到 1 倍时，得分会线性增加。 - $V_2$ 是 70 分界线。得分从 $V_1$ 增加到 $V_2$ 。 - $V_3$ 是 100 分界线。得分从 $V_2$ 增加到 $V_3$ 。 - 在 $V_3$ 到 $V_4$ 范围内，得分始终为 100。 - 超过 $V_4$ 后，得分从 $V_4$ 增加到 $V_5$，达到最大 120 分。 分数变化如下图所示：  **本翻译由 AI 自动生成**