AT_ahc056_a [AHC056A] Grid Turing Robot

「[チューリングマシン](https://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3)」は計算理論で用いられる仮想的な計算機であり、 一次元のテープ上で、**遷移規則**にしたがって**内部状態**（マシンに搭載されたメモリの値）と**ヘッド位置の文字**を書き換えながらヘッドを左右に動かして計算を行うものである。 F社は、その仕組みを模したロボットを開発している。 このロボットは、二次元のグリッド状の盤面上で、**遷移規則**にしたがって**内部状態**と**現在位置の色**を書き換えながら、上下左右に移動することができる。 目的地を指定された順に訪問するよう、このロボットの**遷移規則**を設計してほしい。 開発コストは使用する色数と状態数の和に比例するため、できるだけ小さい和で実現することが望ましい。

$ N\times N $ マスの盤面がある。 左上のマスの座標を $ (0, 0) $ とし、下方向に $ i $ 、右方向に $ j $ 進んだ位置の座標を $ (i, j) $ とする。 $ N\times N $ マスの外周は壁で囲まれており、また、隣接するマスの間にも壁が存在する場合がある。 各マスには色を塗ることができる。 使用する色の総数を $ C $ とし、各色は整数 $ 0,1,\ldots,C-1 $ で表す。 初期状態の盤面の色は自由に設定してよい。 ロボットは、**内部状態** を表す変数を1つ持つ。 この内部状態は整数 $ 0,1,\ldots,Q-1 $ のいずれかの値をとる。 取りうる状態の総数 $ Q $ は自由に設定してよい。 内部状態の初期値は $ 0 $ である。 ロボットは現在位置の色 $ c $ と内部状態 $ q $ に基づいて、次の行動を決定し、以下の3つの操作を同時に行う。 - 現在位置の色を $ A(c, q) $ に塗り替える（現在と同じ色に塗り替えてもよい）。 - 内部状態を $ S(c, q) $ に更新する（現在と同じ内部状態に更新してもよい）。 - $ D(c, q) $ の方向に移動する（上・下・左・右・移動しない）。移動先との間に壁がある場合、ロボットは移動できずその場に留まる。 ここで、 $ A, S, D $ はそれぞれ **遷移規則** を表す関数である。 遷移規則は動作開始前に設計し、動作中に変更することはできない。 また、ロボットの行動は現在位置そのものには依存せず、現在位置の色と内部状態のみによって決定される。 #### ロボットの動作例 >  > > 上図の例ではまず、 $ 3\times 3 $ の盤面が青色に塗られた状態で位置 $ (0, 0) $ から動作を開始し、以下の3つの遷移規則に従って動作する。 > > 1. $ A(青,0)=緑 $ , $ S(青,0)=0 $ , $ D(青,0)=右 $ > 2. $ A(緑,0)=青 $ , $ S(緑,0)=1 $ , $ D(緑,0)=左 $ > 3. $ A(緑,1)=緑 $ , $ S(緑,1)=1 $ , $ D(緑,1)=下 $ > > 最初の3ステップでは遷移規則 1 が繰り返し適用され、緑色に塗り替えつつ右へ進む。3ステップ目では壁にぶつかるため、移動できずその場にとどまる。 4ステップ目は現在位置が緑色のため、遷移規則 2 が適用され、青色に塗り替えながら左に移動し、内部状態が $ 1 $ へと切り替わる。 最後に5ステップ目では、現在位置が緑色かつ内部状態が $ 1 $ のため、遷移規則 3 が適用され、下に移動する。 $ K $ 箇所の目的地の列 $ (x_0,y_0),(x_1,y_1),\ldots,(x_{K-1},y_{K-1}) $ と、ステップ数の上限 $ T $ が与えられる。 ロボットは $ (x_0,y_0) $ のマスからスタートし、 $ T $ ステップ以内に、指定された順にすべての目的地を訪れることを目指す。 ここで、目的地が $ (x_i,y_i) $ のとき、まだ順番が来ていない $ (x_j,y_j) $ （ $ j>i $ ）のマスを先に訪れても、訪問したことにはならない。 実際に $ (x_j,y_j) $ が次の目的地になった時点で、その目的地に改めて到達しなければならない。 すべての目的地を順に訪問できるように、盤面の初期色の配置とロボットの遷移規則を設計せよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ T $ $ v_{0,0} $ $ \cdots $ $ v_{0,N-2} $ $ \vdots $ $ v_{N-1,0} $ $ \cdots $ $ v_{N-1,N-2} $ $ h_{0,0} $ $ \cdots $ $ h_{0,N-1} $ $ \vdots $ $ h_{N-2,0} $ $ \cdots $ $ h_{N-2,N-1} $ $ x_0 $ $ y_0 $ $ \vdots $ $ x_{K-1} $ $ y_{K-1} $ - 盤面の大きさ $ N $ は $ 10\leq N\leq 20 $ を満たす。 - 目的地の個数 $ K $ は $ N\leq K\leq N^2 $ を満たす。 - すべての目的地を順に訪れる最小移動回数を $ X $ とすると、ステップ数の上限 $ T $ は $ X\leq T\leq 2X $ を満たす。 - $ v_{i,0} \cdots v_{i,N-2} $ は長さ $ N-1 $ の `01` からなる文字列であり、 $ j $ 文字目 $ v_{i,j} $ はマス $ (i, j) $ とマス $ (i, j+1) $ の間に壁がある（`1`）かない（`0`）かを表す。 - $ h_{i,0} \cdots h_{i,N-1} $ は長さ $ N $ の `01` からなる文字列であり、 $ j $ 文字目 $ h_{i,j} $ はマス $ (i, j) $ とマス $ (i+1, j) $ の間に壁がある（`1`）かない（`0`）かを表す。 - 全てのマスは互いに到達可能であることが保証されている。 - $ (x_k, y_k) $ は $ k $ 番目の目的地の座標を表し、 $ 0\leq x_k,y_k\leq N-1 $ を満たす。すべての目的地は相異なる。

以下の形式で標準出力に出力せよ。 > $ C $ $ Q $ $ M $ $ s_{0,0} $ $ \cdots $ $ s_{0,N-1} $ $ \vdots $ $ s_{N-1,0} $ $ \cdots $ $ s_{N-1,N-1} $ $ c_0 $ $ q_0 $ $ A(c_0,q_0) $ $ S(c_0,q_0) $ $ D(c_0,q_0) $ $ \vdots $ $ c_{M-1} $ $ q_{M-1} $ $ A(c_{M-1},q_{M-1}) $ $ S(c_{M-1},q_{M-1}) $ $ D(c_{M-1},q_{M-1}) $ - $ C $ は使用する色数であり、 $ 1 \le C \le N^4 $ を満たす必要がある。 - $ Q $ は使用する内部状態数であり、 $ 1 \le Q \le N^4 $ を満たす必要がある。 - $ M $ は出力する遷移規則の行数であり、 $ 0 \le M \le T $ を満たす必要がある。 - $ s_{i,j} $ は初期状態におけるマス $ (i,j) $ の色であり、 $ 0 \le s_{i,j} \le C-1 $ を満たす必要がある。 - 各行 $ c_i $ $ q_i $ $ A(c_i,q_i) $ $ S(c_i,q_i) $ $ D(c_i,q_i) $ は、現在位置の色が $ c_i $ 、内部状態が $ q_i $ のときに適用する遷移規則を表す。 - $ 0\leq c_i\leq C-1 $ 、 $ 0\leq q_i\leq Q-1 $ を満たす必要があり、同じ $ (c_i,q_i) $ の組は高々一度しか出現してはならない。 - 塗り替える色 $ A(c_i,q_i) $ は $ 0 \le A(c_i,q_i) \le C-1 $ を満たす必要がある。 - 新しい内部状態 $ S(c_i,q_i) $ は $ 0 \le S(c_i,q_i) \le Q-1 $ を満たす必要がある。 - 移動方向 $ D(c_i,q_i) $ は以下の5文字のいずれかで表す。 - 上：`U` - 下：`D` - 左：`L` - 右：`R` - 移動しない：`S` $ C\times Q $ は非常に大きくなり得るため、すべての組 $ (c,q) $ に対する遷移規則を出力する必要はない。 シミュレーション中に実際に遭遇する可能性のある組に対する遷移規則のみを出力すればよい。 最大で $ T $ ステップであるため、高々 $ T $ 行の遷移規則を出力すれば十分である。 ただし、実行中に遭遇した $ (c,q) $ に対する遷移規則が出力中に存在しない場合、その時点でロボットの行動は打ち切られる。 [例を見る](https://img.atcoder.jp/ahc056/zUbWUSnS.html?lang=ja&seed=-1&output=sample)

### 得点 使用する色数を $ C $ 、状態数を $ Q $ 、ステップ数の上限 $ T $ 以内に訪問できた目的地の数を $ V $ とする。 このとき、以下の絶対スコアが得られる。 - $ V=K $ の場合、 $ C+Q $ - $ V gi and can_move(i, j, 'U'): d = 'U' elif i < gi and can_move(i, j, 'D'): d = 'D' elif j > gj and can_move(i, j, 'L'): d = 'L' elif j < gj and can_move(i, j, 'R'): d = 'R' if d == 'S': break rules.append((s[i][j], 0, s[i][j], 0, d)) di, dj = DIJ[d] i, j = i + di, j + dj # 出力 print(C, Q, len(rules)) for r in range(N): print(' '.join(map(str, s[r]))) for c, q, A, S, D in rules: print(c, q, A, S, D) ``` ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc056/zUbWUSnS.html?lang=ja): ローカル版より高性能でアニメーション表示が可能です。 - [ローカル版](https://img.atcoder.jp/ahc056/zUbWUSnS.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc056/zUbWUSnS_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。 ### Sample Explanation 1 これは、問題文中のロボットの動作例に対応する入出力である。説明用のものであり、入力の制約は満たしていない。