AT_ahc034_a [AHC034A] Leveling with a Dump Truck

题目描述

现有一 $N \times N$ 的土地。定义 $(i,j)$ 为从上起第 $i+1$ 行,左起第 $j+1$ 列的单元格。 定义 $(i,j)$ 的高度为 $h_{i,j}$,保证各单元格高度之和为 $0$。 在最开始时,有一空挖掘机在 $(0,0)$ 处。你可以进行以下三种操作合计不超过 $100000$ 次: - 往挖掘机上装 $d$ 单位的土。该操作代价是 $d$。 - 从挖掘机上卸下 $d$ 单位的土。该操作代价是 $d$。需要保证操作后挖掘机所装土的数量不为负数。 - 把挖掘机向上下左右其中一个方向移动一格。该操作代价是 $d+100$,其中 $d$ 表示挖掘机所装土的量。 试给出一个操作序列,让所有单元格高度变为 $0$,并使操作总代价最小。

输入格式

第一行一个数 $N$。 随后 $N$ 行,每行 $N$ 个数,代表各单元格初始高度。

输出格式

记 $T$ 为操作次数。 输出共 $T$ 行,每行一个操作。 + 从当前位置将泥土装载 $d$ 单位到挖掘机上:`+d` + 将 $d$ 单位泥土从挖掘机卸到当前位置:`-d` + 将挖掘机移动到相邻的方格:`U`、`D`、`L` 和 `R`

说明/提示

保证 $N=20$ 且 $-100 \le h_{i,j} \le 100$。 [Web](https://img.atcoder.jp/ahc034/vImT4eac.html?lang=en):一个可视化工具。 translated by @[heyuguo](/user/66964)