/
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 550 点
問題文
大人気アイドルグループである Bit♡Beat はとても広い会場でライブをすることになりました。
ライブ会場は南北に H 行、東西に W 列のグリッドに区切られており、グリッドのしきりにあたる部分に通路があります。(詳しくは入出力例を参考にしてください。)
通路同士の交点にあたる場所にそれぞれ (H+1)(W+1) 個のステージがあり、最も北西にあるステージから南に r 本、東に c 本通路を進んだ先のステージをステージ (r,c) (0 \le r \le H , 0 \le c \le W) と表記します。
プロデューサーであるあなたは、アイドルがライブ中にステージ (0,0) から出発して全ての通路を 1 回以上通ってから再びステージ (0,0) に戻ってくるような経路を通るような経路を考えています。しかし、時間の都合上そのような経路のうちステージ間の移動回数が少ないようなものを採用したいと考えました。
(0,0) から出発して全ての通路を 1 回以上通ってから再びステージ (0,0) に戻ってくるような経路のうち、ステージ間の移動回数が最小となる経路を一つ求めてください。
制約
- 1\le H ,W\le 100
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
H W
出力
ステージ間の移動の最小回数を K として、以下で定義される長さ K の文字列 S を出力せよ。
- i 回目の移動前がステージ (r,c) 、移動後がステージ (r',c') だとすると、 S の i 文字目は以下のように定義される。
- r+1=r' のとき: S_i=
D - r-1=r' のとき: S_i=
U - c+1=c' のとき: S_i=
R - c-1=c' のとき: S_i=
L
- r+1=r' のとき: S_i=
入力例 1
1 2
出力例 1
RRDLUDLU
ライブステージは以下の画像のようになります。

例えばステージ (0,0) からスタートして以下の画像の通路に書かれた番号順に移動することで 8 回の移動で全ての通路を通ることができます。

8 回未満の移動で全ての通路を通りステージ (0,0) に戻ることはできないので、 RRDLUDLU を出力すると正解となります。
また、RRDLUDLU のほかにも RDRULDLU などを出力しても正解となります。
入力例 2
1 1
出力例 2
DRUL
入力例 3
2 2
出力例 3
DDRUURDDLURLLURL