/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
ストーリー
AtCoder社の高橋社長は、オフィスの模様替えのために全ての床の色を塗り替えたいと考えている。 しかし、オフィスは広く、全ての床の色を塗り替えるには時間がかかる。
そこで高橋社長は「インクシューター」という装置を開発した。 インクシューターは、時間経過によってパワーが溜まり、現在のパワーを半分消費することで、パワーに応じた距離の直線状に床を一気に塗ることができる。
インクシューターを利用して、全ての床を効率的に塗りつぶす方法を考えてほしい。
問題文
N \times N の盤面がある。左上のマスを (0,0) とし、下方向に i マス、右方向に j マス進んだ位置のマスを (i,j) とする。 N \times N マスの外部は全て壁で覆われており、通過できない。 盤面には床マスと壁マスがあり、 N \times N マスのうち、 M 個が壁マスである。 全ての床マスは連結であることが保証されている。
あなたは初期位置 (s_i, s_j) にいる。 また、あなたは「インクシューター」という装置を持っている。インクシューターはパワー値 P を持ち、初期状態では P=0 である。
あなたは以下の3種類の行動のいずれかを最大 T 回まで行うことができる。
-
移動： 上下左右の方向を指定して1マス移動する。ただし、移動先が壁マスまたは盤面の外となる場合、移動は行われない。その後、 P を P+1 に更新する。
-
インクの発射： 上下左右の方向を指定し、インクシューターを用いてインクを発射する。
インクはあなたの現在位置から指定方向に最大 P マスまで進み、（あなたの現在位置を含む）通過した床マスを全て塗りつぶす。ただし、壁を超えて塗りつぶすことはできない。
より厳密には、 k = 0,1,2, \ldots, P の順に以下の処理を行う。- あなたの現在位置から指定方向に k マス進んだ位置を (i,j) とする。
- (i,j) が盤面の外、または壁マスである場合、以降の k について処理を行わずに終了する。
- (i,j) がまだ塗りつぶされていない床マスである場合、 塗りつぶす。
その後、 P を \lfloor P/2 \rfloor + 1 に更新する。
-
パス： P を P+1 に更新する。
なるべく多くの床マスを塗りつぶせるように、また全ての床マスを塗りつぶせるならばなるべく早く塗りつぶせるように、行動を決定せよ。
得点
全ての行動終了後に塗りつぶせなかった床マスの数を X 、行動回数を K としたとき、以下の得点が得られる。
- X > 0 の場合、N^2 - X
- X = 0 の場合、N^2 + T - K
得点は高ければ高いほどよい。
合計で 100 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。
入力
盤面のサイズ N 、壁マスの個数 M 、最大行動回数 T 、初期位置 (s_i, s_j) 、盤面の情報 S が以下の形式で標準入力から与えられる。
N M T s_i s_j
S_{0,0}S_{0,1}S_{0,2}\cdotsS_{0,N-1}
S_{1,0}S_{1,1}S_{1,2}\cdotsS_{1,N-1}
\vdots
S_{N-1,0}S_{N-1,1}S_{N-1,2}\cdotsS_{N-1,N-1}
- N = 20
- 0 \leq M \leq 30
- T = 250
- 0 \leq s_i, s_j < N
- S_{i,j} が
.の場合 (i,j) は床マスであり、#の場合 (i,j) は壁マスである。 - 初期位置 (s_i, s_j) は床マスである。
- 盤面の全ての床マスは連結である。
出力
行動回数を K としたとき、以下の形式で標準出力に出力せよ。
K op_1 op_2 \vdots op_K
行動回数 K は、 K \leq T を満たす必要がある。 op_i は i 回目の行動を表し、行動の種類に応じて以下の形式で出力せよ。
移動：
1 d
ここで d は移動方向を表す文字で、上:U、下:D、左:L、右:R のいずれかである。
インクの発射：
2 d
ここで d はインクの発射方向を表す文字で、上:U、下:D、左:L、右:R のいずれかである。
パス：
3
入力生成方法
- 初期位置 (s_i, s_j) を盤面からランダムに選ぶ。
- 壁マスの個数 M を 0 以上 30 以下の整数からランダムに選ぶ。
- 盤面 S を全て床マスで初期化する。
- 盤面 S の壁マスが M 個になるまで、ランダムなマスを壁マスにする操作を繰り返す。ただし、以下のいずれかの条件を満たす場合は操作を行わずに、再度マスを選びなおす。
- 選んだマスが既に壁マスである。
- 選んだマスが初期位置 (s_i, s_j) である。
- 選んだマスを壁マスにした場合に、盤面の全ての床マスが連結でなくなる。
ツール(入力ジェネレータ・ビジュアライザ)
- Web版: ローカル版より高性能でアニメーション表示と手動プレイが可能です。
- ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。
- Windows用のコンパイル済みバイナリ: Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。
コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。
入力例1
20 15 250 0 0 .................... ........#........... ..........#......... .................... .................... .#.................. ..................#. .................... .................... .................... ..#...##............ ................#... .................... .....#.........#.... ...........#........ .................... .............#....#. ..#.............#... .................... ....................
出力例1
9 1 R 2 R 1 D 2 D 1 L 2 L 1 U 2 U 3