AT_rcl_contest_2020_final_b ハイパーお掃除ロボット
Description
[problemUrl]: https://atcoder.jp/contests/rcl-contest-2020-final/tasks/rcl_contest_2020_final_b
$ N $ 行 $ N $ 列のグリッドがあります。上から $ i $ 行目、左から $ j $ 列目のセルを $ (i,\ j) $ と表します。
各セルの上には、`A`から`Z`までのいずれかの文字が1つ書いてあるシートが1枚置かれています。 さらに、グリッドのうち、1個のセルには球状のお掃除ロボットXがいて、それ以外の $ P $ 個のセルには柱があります。
あなたは柱を移動させつつロボットを上下左右に転がして、ロボットにシートを回収させます。厳密には、あなたは最大で $ M $ 回、以下のいずれかの操作を実行できます。
- **柱を動かす**: 任意の1つの柱を別のセルへ移動します。ただし、ロボットまたは柱が存在するセルを移動先として選ぶことはできません。
- **ロボットを転がす**: ロボットを上下左右のいずれかの方向に転がします。
- ロボットは指定された方向に転がり続けて、柱が存在するセルにぶつかると柱の直前のセルで止まります。ぶつかる柱がない場合、グリッド外に出る直前のセルで止まります。
- その後、止まったセルに文字が書いてあるシートがあれば、ロボットにそれを回収させます。ただし、一度シートを回収させたセルに再度止まった場合、シートを回収させることはできません。
全ての操作を終えた後に、ロボットに回収させた順にシートを並べて、「連続した同じ文字の長さの二乗」の和のスコアを獲得します。
（例えば、シートを `A`, `B`, `B`, `B`, `A`, `B`の順に回収させた場合、スコアは \\(1^2 + 3^2 + 1^2 + 1^2 = 12 \\)です。）
うまくロボットと柱を動かすことで、スコアを最大化してください。
各テストケースの得点およびこの問題の得点は、次のように計算されます。
- 1つのテストケースでは、操作を終えた後のスコアがそのまま得点になります。
- テストケースは全部で $ 50 $ 個あります。各テストケースの得点の合計が、この問題の得点になります。
Input Format
入力は以下の形式で標準入力から与えられます。
> $ N $ $ P $ $ M $ $ row_{0} $ \\(\\vdots\\) $ row_{N-1} $ $ sheets_{0} $ \\(\\vdots\\) $ sheets_{N-1} $
- $ N $ はグリッドの大きさを表す整数で、$ N\ =\ 40 $ を満たします。
- $ P $ は柱の数を表す整数で、$ P\ =\ 300 $ を満たします。
- $ M $ は問題文中で定められた操作を実行できる回数の最大値で、$ M\ =\ 1000 $ を満たします。
- $ row_{i} $ は 長さ $ N $ の文字列で、その各文字は `o`, `x`, `-`のいずれかです。$ row_{i} $ の $ j $ 番目の文字（\\( 0 \\leq i,j \\lt N \\)） が
- `o` なら $ (i,j) $ にロボットが存在すること
- `x` なら $ (i,j) $ に柱が存在すること
- `-` なら $ (i,j) $ にロボットも柱も存在しないこと
を表します。また、$ row_0 $ から $ row_{N-1} $ のうち、`o`は1文字、`x`はちょうど $ P $ 文字であることが保証されます。
- $ sheets_{i} $ は 長さ $ N $ の文字列で、その各文字は `A` から `Z`のいずれかです。 $ sheets_{i} $ の $ j $ 番目の文字（\\( 0 \\leq i,j \\lt N \\)）は、$ (i,j) $ に置かれたシートに書いてある文字を表します。
Output Format
最大$ M $ 行出力してください。上から順に、実行する操作を出力してください。
- **柱を動かす**場合、行の先頭に`P`を出力し、柱が存在するセル$ (r_{1},\ c_{1}) $ と 移動先のセル$ (r_{2},\ c_{2}) $を次のようにスペース区切りで出力してください（\\( 0 \\leq r\_1, c\_1, r\_2, c\_2 \\lt N \\) ）。操作前に $ (r_{1},\ c_{1}) $に柱がない場合、および$ (r_{2},\ c_{2}) $にロボットか柱が存在する場合、WA となります。 > P $ r_1 $ $ c_1 $ $ r_2 $ $ c_2 $
- **ロボットを転がす**場合、転がす方向を表す文字を `UDLR` （それぞれ上下左右に対応します）の中からひとつ出力してください。
```
[UDLR]
```
Explanation/Hint
### テストケースの生成について
各ケースはテストケースジェネレータによって生成されています。
テストケースジェネレータはページ下部のリンクより提供しています。
ロボットと柱の初期配置、およびシートに書いてある文字は一様乱数にしたがって生成されます。厳密にはテスターの実装を見てください。
### ジェネレータとテスターとサンプル入力データ
テストケースジェネレータ・テスター・サンプル入力データを次のリンクから提供しています。
[ジェネレータ・テスター・サンプル入力データ](https://github.com/recruit-communications/rcl-contest-2020/tree/master/final_B/tester)
### ビジュアライザ
入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。
- このビジュアライザはデスクトップ版の [Google Chrome](https://www.google.co.jp/chrome/browser/desktop/index.html) および [Mozilla Firefox](https://www.mozilla.org/firefox/new/) の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。
- このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
- このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。
[ビジュアライザ](https://github.com/recruit-communications/rcl-contest-2020/tree/master/final_B/visualizer)
### Sample Explanation 1
このケースは説明用のもので、入力の制約を満たしていません。 入出力例の説明をします。 プログラムの出力 説明 ロボットと柱の位置 置かれたシート 拾ったシート 入力で与えられた最初の状態です。ロボットは最初 $ (1,1) $にいて、`A`と書いてあるシートの上にいますが、このシートは現時点で拾えないことに注意してください。 ```
```
---- -o-- x--- -x-- ``` ```XYZX ZAYX ZBZB XYZX ``` なし ```D ``` ロボットは $ (1,1) $ から下に移動し続け、$ (3,1) $ にある柱にぶつかり、$ (2,1) $ で止まります。そこに置かれた `B`と書いてあるシートを回収させます。 ```---- ---- xo-- -x-- ``` ```XYZX ZAYX Z ZB XYZX ``` ```B ``` ```R ``` ロボットは $ (2,1) $ から右に移動し続け、グリッドの端である $ (2,3) $ で止まります。そこに置かれた `B`と書いてあるシートを回収させます。 ```---- ---- x--o -x-- ``` ```XYZX ZAYX Z Z XYZX ``` ```BB ``` ```L ``` ロボットは $ (2,3) $ から左に移動し続け、$ (2,0) $ にある柱にぶつかり、$ (2,1) $ で止まります。ここでは既にシートを回収させているため、再度シートを回収させることはできません。 ```---- ---- xo-- -x-- ``` ```XYZX ZAYX Z Z XYZX ``` ```BB ``` ```P 2 0 0 1 ``` $ (2,0) $ に置かれた柱を、$ (0,1) $ へ移動します。 ```-x-- ---- -o-- -x-- ``` ```XYZX ZAYX Z Z XYZX ``` ```BB ``` ```U ``` ロボットは $ (2,1) $ から上に移動し続け、$ (0,1) $ にある柱にぶつかり、$ (1,1) $ で止まります。そこに置かれた `A`と書いてあるシートを回収させます。あなたはあと1回操作をすることもできますが、途中でやめることもできます。 ```-x-- -o-- ---- -x-- ``` ```XYZX Z YX Z Z XYZX ``` ```BBA ``` この場合のスコアは \\( 2^2 + 1^2 = 5 \\)点となります。 ```