AT_rco_contest_2017_qual_b Food Collector

在一张 $H$ 行 $W$ 列的方形地图上，有两个类型的格子：障碍物和空地。有些空地上放置了不超过一个食物。 地图的行编号从 $1$ 开始，列编号也从 $1$ 开始。在地图的第 $sr$ 行第 $sc$ 列有一只小狗。小狗可以在 $0, 1, 2, \ldots$ 秒时刻向相邻的非障碍物格子移动，并且移动是瞬时完成的。当狗移动到有食物的格子时，它一定会吃掉食物。食物被吃掉后会消失，你将获得食物对应的分数。食物 $i$ 的初始分数为 $F_i$，每经过 $1$ 秒，分数减少 $D_i$。这种减少在小狗移动和获取食物后立即发生。 请你设计小狗在从 $0$ 到 $K-1$ 秒内的移动方案，以使得获得的总分数最大化。

输入由以下内容组成（均为整数）： > $H$ $W$ $K$ $sr$ $sc$ $s_1$ $s_2$ ... $s_H$ $N$ $fr_1$ $fc_1$ $F_1$ $D_1$ ... $fr_N$ $fc_N$ $F_N$ $D_N$ - $H = W = 50$ - $K = 2500$ - 起始行 $1 \leq sr \leq H$ - 起始列 $1 \leq sc \leq W$ - $s_i$ 表示地图的第 $i$ 行，由 `#` 表示障碍物、`.` 表示空地的字符串。长度为 $W$。 - $N$ 数目，表示总共分布了多少个食物。 - 食物所在行 $1 \leq fr_i \leq H$ - 食物所在列 $1 \leq fc_i \leq W$ - 食物的初始分数 $0 \leq F_i \leq 10^5$ - 分数每秒减少量 $0 \leq D_i \leq 100$ - $(sr, sc)$ 和 $(fr_i, fc_i)$ 的位置不相同并且都是空地。 - 地图四边（第一行、最后一行、第一列和最后一列）全部为障碍物。 - 任何空地之间都可以通过相邻空地到达。

输出一个长度为 $K$ 的字符串 $movement$，表示狗的移动路径： - $movement$ 是描述小狗行动的字符串，由以下字符组成： - `U` 向上移动一格。 - `D` 向下移动一格。 - `L` 向左移动一格。 - `R` 向右移动一格。 - `-` 表示保持原地不动。

### 背景 汪汪！ ### 测试用例的生成和可视化 生成器和测试器可以通过以下链接获取： [生成器和测试器](https://gist.github.com/tomerun/e04223ea550b9ca7f1c5065430c29569) ### 示例解释 注意：以下示例不符合测试用例的严格条件，仅用于说明。 假设地图和初始位置如下图所示，其中 `S` 是小狗的起点，`1` 和 `2` 分别表示放置的食物，而 `X` 是小狗最终的停留位置。 ``` ########## ###.....## ##2..##.1# #...####S# #..X###### #...###### #...###### #...###### #...###### ########## ``` 在 $0$ 秒时，小狗吃掉了食物 $1$，在 $10$ 秒时吃掉了食物 $2$。再过 $2$ 秒，小狗回到食物 $1$ 的位置，但食物 $1$ 已经消失，所以没有得分变化。从 $16$ 秒开始，小狗试图朝障碍物方向移动，但是不会成功。此时的得分计算如下： - 在 $0$ 秒时，小狗得到了食物 $1$ 的分数 $10000$。 - 在 $10$ 秒时，小狗得到了食物 $2$ 的分数 $-6$（由于开始时分数低于消耗速度，最终变为负分）。 - 总分数为 $9994$，除以 $10000$ 后四舍五入到整数，即 $1$。 **本翻译由 AI 自动生成**