102277: [AtCoder]ABC227 H - Eat Them All

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $600$ points

Problem Statement

We have a grid with $3$ horizontal rows and $3$ vertical columns. Let $(i, j)$ denote the square at the $i$-th row from the top and $j$-th column from the left. $(i, j)$ contains $A_{i,j}$ cans of cat food.

Snuke is now on $(1,1)$. He will repeat the following action.

  • Consume one can on the square he is on, and move up, down, left, or right to an adjacent square.

When there is no more can on the square he is on, he will end this process.

Is it possible that all of the conditions below are satisfied at the end of the process? If it is possible, show one sequence of actions that make it happen.

  • Snuke is at $(1,1)$.
  • There is no more can on every square.

Constraints

  • $1 \leq A_{i,j} \leq 100$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$A_{1,1}$ $A_{1,2}$ $A_{1,3}$
$A_{2,1}$ $A_{2,2}$ $A_{2,3}$
$A_{3,1}$ $A_{3,2}$ $A_{3,3}$

Output

If it is impossible that the conditions are satisfied, print NO.

If it is possible, print a string $S$ consisting of L, R, U, D. The $i$-th character of $S$ should represent the $i$-th action of Snuke, where L, R, U, D means moving one square left, right, up, down, respectively.

Sample Input 1

1 1 1
1 1 1
1 2 1

Sample Output 1

DDRUDRUULL

Note that Snuke must be back on $(1, 1)$ in the end.

There are also other correct outputs, such as RRDDLUDLUU.

Sample Input 2

2 4 2
2 1 1
1 1 2

Sample Output 2

NO

It is impossible to achieve the objective, so print NO.

Sample Input 3

2 2 3
2 1 2
1 3 2

Sample Output 3

DUDDRUDRLRUULRDULL

Input

题意翻译

现有一个 $3\times 3$ 的矩阵，其中坐标为 $(i,j)$ 的格子里放着 $a_{i,j}$ 个罐头。 现在 $(1,1)$ 位置有一只狐狸，它要吃罐头。每一步它会这样操作： - 吃掉当前格子上的一个罐头。 - 向上下左右任意一个方向移动一格，不能不动也不能走出边界。 当它到达一个格子时没有罐头可吃，它就会停止移动。 问是否能满足下列要求： - 吃完所有罐头。 - 最终停在 $(1,1)$。 如果不能，输出 `NO`；否则输出移动序列，上下左右分别用 `UDLR` 表示。 保证每个格子上初始罐头数量不超过 $100$ 个。

Output

得分：600分 部分 问题描述 我们有一个具有3行水平和3列垂直的网格。让$(i, j)$表示从顶部的第$i$行和从左的第$j$列的正方形。$(i, j)$包含$A_{i,j}$罐猫食。 Snuke现在在$(1,1)$。他将重复以下操作。 * 在他所在的正方形上吃掉一个罐头，然后向上、下、左或右移动到相邻的正方形。 当他所在的正方形上没有罐头时，他将结束这个过程。 是否有可能在过程结束时都满足以下条件？如果可能，请显示一个使其发生的操作序列。 * Snuke在$(1,1)$。 * 每个正方形上都没有罐头了。 部分 约束 * $1 \leq A_{i,j} \leq 100$ * 输入中的所有值都是整数。 部分 输入 输入格式如下： ```bash $A_{1,1}$ $A_{1,2}$ $A_{1,3}$ $A_{2,1}$ $A_{2,2}$ $A_{2,3}$ $A_{3,1}$ $A_{3,2}$ $A_{3,3}$ ``` 部分 输出 如果不可能满足条件，请打印`NO`。 如果可能，请打印一个由`L`，`R`，`U`，`D`组成的字符串$S$。$S$的第$i$个字符应表示Snuke的第$i$个操作，其中`L`，`R`，`U`，`D`分别表示向左移动一个正方形、向右移动一个正方形、向上移动一个正方形、向下移动一个正方形。 部分 样例输入1 ```bash 1 1 1 1 1 1 1 2 1 ``` 部分 样例输出1 ```bash DDRUDRUULL ``` 注意，Snuke最终必须回到$(1, 1)$。 还有其他正确的输出，例如`RRDDLUDLUU`。 部分 样例输入2 ```bash 2 4 2 2 1 1 1 1 2 ``` 部分 样例输出2 ```bash NO ``` 无法实现目标，因此打印`NO`。 部分 样例输入3 ```bash 2 2 3 2 1 2 1 3 2 ``` 部分 样例输出3 ```bash DUDDRUDRLRUULRDULL ```

Source/Category

加入题单

算法标签：