問題文
やさしいわりとねこくんは、ねこたちのためにとても豪華なキャットタワーを建てることにしました。
建設予定地は 行 列のマス目で、はじめはすべてのマスの高さが です。上から 行目、左から 列目のマスを とします。わりとねこくんは、マス の最終的な高さを にしたいと考えています。
盤面の各マスに、L、R、U、D のいずれかの杭を ちょうど1本 打ち込みます。盤面の外に杭を打ち込むことはできません。杭の配置は、次の条件を満たす必要があります。
- 各行について、左から右に
LとRの杭だけを取り出します。Lを開き括弧(、Rを閉じ括弧)とみなすと、正しい括弧列になっていなければなりません。 - 各列について、上から下に
UとDの杭だけを取り出します。Uを開き括弧(、Dを閉じ括弧)とみなすと、正しい括弧列になっていなければなりません。
空の括弧列も正しい括弧列とします。
すべての杭を打ち込んだあと、各括弧列で対応する開き括弧と閉じ括弧をペアにし、次のように高さを増やします。
- 同じ行で対応する
LとRのペアごとに、その行で2本の間にあるすべてのマスの高さを 増やします。 - 同じ列で対応する
UとDのペアごとに、その列で2本の間にあるすべてのマスの高さを 増やします。
どちらの場合も、そのペアの両端のマスには高さを加えません。 本の間にあるマスには、そこに打ち込まれた杭の種類にかかわらず高さを加えます。あるマスが複数のペアの間にある場合は、ペアごとに高さが ずつ増えます。
建設後のすべてのマスの高さが指定どおりになるような、杭の配置を つ求めてください。
制約
- 入力はすべて整数
- 条件を満たす杭の配置が少なくとも1つ存在する
入力
入力は以下の形式で標準入力から与えられます。
出力
条件を満たす杭の配置を、長さ の文字列 個として、上の行から順に1行に1個ずつ出力してください。 行目の 文字目は、マス に打ち込む杭を表す L、R、U、D のいずれかとします。
条件を満たす配置が複数ある場合は、どれを出力してもかまいません。
入出力例
入力例 1
4
0 1 1 0
0 2 2 0
0 2 2 0
0 1 1 0
出力例 1
LUUR
LUUR
LDDR
LDDR
各行では、1列目と4列目の杭がペアになり、2列目と3列目の高さがそれぞれ 増えます。
2列目と3列目では、どちらも1行目と4行目の杭、2行目と3行目の杭がそれぞれペアになります。外側のペアによって、2行目と3行目の高さがさらに 増えます。内側のペアの間にはマスがありません。
入力例 2
2
0 0
0 0
出力例 2
LR
LR
各行の L と R は隣り合っており、その間にマスがありません。したがって、すべてのマスの高さは のままです。
入力例 3
4
0 1 1 0
0 0 0 0
0 1 2 1
0 0 0 0
出力例 3
LLRR
LRUU
LLRR
LRDD
1行目と3行目では、1列目と4列目の杭がペアになり、2列目と3列目の高さを 増やします。また、3列目と4列目では、2行目の U と4行目の D がペアになり、3行目の高さを 増やします。
例えば、マス の高さは横と縦のペアからそれぞれ ずつ増えて になります。盤面の右端にあるマス の高さは、縦のペアによって になります。
スペシャルジャッジ問題です。
参加受付は終了しました。
ログインして解答を提出
解答の提出や採点結果の確認には、ログインが必要です。
ログインする