/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
縦 3 行、横 3 列のマス目があります。上から i 行目、左から j 列目のマスを (i,j) と書くことにします。(i,j) には A_{i,j} 個の猫缶が置かれています。
すぬけ君は現在 (1,1) にいます。すぬけ君は以下の行動を繰り返します。
- すぬけ君が現在いるマスに置かれている猫缶を 1 つ食べた後、隣接するマスに移動する
すぬけ君は、現在いるマスに猫缶が残っていないとき行動を終了します。
行動を終了した時に以下の条件が全て満たされることは可能ですか？可能ならばすぬけ君の行動の一例を示してください。
- すぬけ君は (1,1) にいる。
- どのマスにも猫缶が残っていない。
制約
- 1 \leq A_{i,j} \leq 100
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
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 文字目はすぬけ君の i 回目の行動の内容を表し、L は 1 つ左のマス、R は 1 つ右のマス、U は 1 つ上のマス、D は 1 つ下のマスに移動することをそれぞれ意味する。
入力例 1
1 1 1 1 1 1 1 2 1
出力例 1
DDRUDRUULL
すぬけ君は終了時点で (1,1) に戻っていなければいけないことに注意してください。
なお、RRDDLUDLUU などの出力も正しいです。
入力例 2
2 4 2 2 1 1 1 1 2
出力例 2
NO
目標を達成することは不可能なので、NO と出力してください。
入力例 3
2 2 3 2 1 2 1 3 2
出力例 3
DUDDRUDRLRUULRDULL
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