AT_stage0_2021_a Patrolling

[problemUrl]: https://atcoder.jp/contests/stage0-2021/tasks/stage0_2021_a $ N\times\ N $ マスの地図が与えられる。 一番左上のマスを $ (0,0) $ とし、そこから下方向に $ i $ 回、右方向に $ j $ 回移動した先のマスを $ (i,\ j) $ とする。 各マスは障害物(`#`)もしくは道路であり、道路マス上を上下左右に移動することが出来る。 各道路マスは`5`-`9`の数字で表され、隣接マスからそのマスへの移動にかかる時間を表している。 位置 $ (i,\ j) $ の道路マス上に居る時、以下の条件を満たす道路マス $ (i',j') $ を「視界に入る」と定義する。 - $ i=i' $ であり、全ての $ \min(j,j')\leq\ j''\leq\max(j,j') $ に対して $ (i,j'') $ が道路マス、もしくは - $ j=j' $ であり、全ての $ \min(i,i')\leq\ i''\leq\max(i,i') $ に対して $ (i'',j) $ が道路マス。 例えば下図では灰色のマスが障害物を、白色と薄黄色のマスが道路を表しており、緑丸の地点に居るときに視界に入る道路マスが薄黄色で塗られている。  指定された道路マス $ (si,sj) $ からスタートして、道路マス上を上下左右に移動することを繰り返して $ (si,sj) $ に戻ってくるような巡回ルートのうちで、全ての道路マスが少なくとも一回は視界に入るようなもののうち、出来るだけ総移動時間の短いものを求めよ。 同じマス上を何度も移動してよく、Uターンすることも可能である。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ si $ $ sj $ $ c_0 $ $ \vdots $ $ c_{N-1} $ - $ N $ は $ 49 $ 以上 $ 69 $ 以下の奇数。 - $ si,\ sj $ は $ 0\leq\ si\leq\ N-1 $、$ 0\leq\ sj\leq\ N-1 $ を満たす整数値。 - 各 $ c_i $ は`5`, `6`, `7`, `8`, `9`, `#` からなる長さ $ N $ の文字列であり、$ j $ ($ 0\leq\ j\leq\ N-1 $) 文字目の文字は位置 $ (i,\ j) $ のマスの情報を以下のように示している。 - `#` はそのマスに障害物があることを表す。$ (si,\ sj) $ のマスには障害物が無いことが保証されている。 - `5`から`9`はそのマスが道路であることを示しており、その数字はそのマスへの移動にかかる時間を表している。

$ (i,\ j) $ から $ (i-1,j) $, $ (i+1,j) $, $ (i,j-1) $, $ (i,j+1) $ への移動をそれぞれ `U`, `D`, `L`, `R` として巡回ルートを文字列で表し、標準出力に一行で出力せよ。

### ストーリー 高橋市警では警察官の人手不足解消のために、自動運転の無人パトカーによる自動パトロールが実施されることになった。 無人パトカーには屋根の上に高性能な全方位カメラが取り付けられており、現在位置からの直線上にある道路全体を一度に見渡すことが出来、画像処理技術を用いて異変が無いかを自動検出する。 市民の安全で安心な暮らしを守るため、市内の隅から隅まで少なくとも一度は見渡すことが出来るような巡回ルートを設定したい。 そのような巡回ルートの中で出来るだけ短いものを求めてほしい。 ### 得点 道路マスの総数を $ r $、少なくとも一回は視界に入った道路マスの総数を $ v $、巡回ルートの総移動時間を $ t $ とすると、以下の得点が得られる。 - $ v\