AT_masters2025_qual_a Ore Rolling (A)

$ N \times N $ のマス目で表される洞窟がある。 一番左上のマスの座標を $ (0,0) $ とし、そこから下方向に $ i $ マス、右方向に $ j $ マス進んだ先のマスの座標を $ (i,j) $ とする。 洞窟の周囲は壁で囲まれており、外に出ることはできない。 洞窟内には岩と $ M $ 種類の鉱石が散らばっている。 また、洞窟内の異なる $ M $ 個のマスには穴があり、 $ i $ 種類目の鉱石を全て $ i $ 番目の穴に落としたい。 **岩については、どの穴に落としてもよく、また洞窟内に放置してもよい。** あなたは以下の操作を 最大で $ 10000 $ 回 行うことができる。 1. 上下左右に隣接するマスへ移動する。**移動先に穴・岩・鉱石があっても移動できる。** 2. 現在位置にある岩・鉱石を上下左右に隣接するマスへ運ぶ。**運ぶ先にすでに別の岩・鉱石があってはならない。運ぶ先は穴でもよい。** 運んだ先が穴であった場合、岩・鉱石は穴に落ちて取り除かれる。あなたの現在位置は運んだ先のマスになる。 3. 現在位置にある岩・鉱石を、上下左右のいずれかの方向に転がす。転がした岩・鉱石は、岩・鉱石・壁にぶつかって止まるか、穴に落ちるまで一直線に転がる。あなたの現在位置は変化しない。 転がす操作は、より詳細には以下の繰り返しによって処理される。 1. 転がっている方向に隣接するマスが穴である場合、岩・鉱石は穴に落ちて取り除かれる。 2. 転がっている方向に隣接するマスに岩・鉱石がある、または $ N \times N $ の外に出る場合、現在のマスで停止する。 3. 上記のどちらにも該当しない場合、隣接するマスへ移動し、処理を繰り返す。 転がる速度は非常に速いため、あなたの次の行動の前に必ず停止するか、穴に落ちて取り除かれる。 できるだけ少ない行動回数ですべての鉱石を対応する穴に落としてほしい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ C_0 $ $ \vdots $ $ C_{N-1} $ - 盤面の大きさ $ N $ は、すべてのテストケースにおいて $ N = 20 $ で固定されている。 - 鉱石の種類数 $ M $ は、問題ごとに固定されている。詳しくは 「入力生成方法」 の項目を参照せよ。 - 各 $ i = 0, 1, \dots, N-1 $ に対し、 $ C_i $ は長さ $ N $ の文字列であり、その $ j $ 文字目は以下のようにマス $ (i, j) $ の初期状態を表す。 - `@`: 岩が存在する。 - `a`-`z`: 鉱石が存在する。 - `A`-`Z`: 穴が存在する。 - `.`: 何も存在しない。 鉱石と穴はアルファベットの大文字・小文字が対応している。 たとえば、文字 `a` で表される鉱石を落とすべき穴は、文字 `A` で表される。 最初の $ M $ 個のアルファベットが使用され、同じ種類の鉱石は複数存在する可能性があるが、同じ種類の穴は必ず 1 つだけである。 あなたは初期状態で穴 `A` のマスにいる。

$ t $ 手目の操作は、行動の種類番号 $ a_t \in \{1,2,3\} $ (1:移動、2:運ぶ、3:転がす) と上下左右の方向を表す文字 $ d_t \in \{U,D,L,R\} $ のペア $ (a_t, d_t) $ で表される。 例えば、 $ (3, R) $ は現在位置にある岩・鉱石を右方向に転がす操作である。 このとき、以下の形式で標準出力に出力せよ。 > $ a_0 $ $ d_0 $ $ \vdots $ $ a_{T-1} $ $ d_{T-1} $

### 得点 出力した行動列の長さを $ T (\leq 10000) $ 、初期盤面における鉱石の総数を $ K $ 、正しい穴に落とすことができた鉱石の総数を $ A $ としたとき、以下の得点が得られる。 - $ A=K $ の場合、 $ \mathrm{round}(10^6\times(1+\log_2{\frac{10000}{T}})) $ - $ A