AT_ahc067_a [AHC067A] Castle Renovation with Linked Doors

魔王高橋くんのもとに、勇者青木くんが魔王城へ近づいているとの知らせが入った。 魔王は、勇者が玉座へ到達するまでの時間を少しでも稼ぐため、城内に連動式の扉とスイッチを設置して改造することにした。 ただし、魔王軍には勇者のスパイが潜入しているため、改造計画は勇者に筒抜けである。 さらに勇者は非常に賢く、玉座へ到達可能であれば、可能な限り少ない行動回数でたどり着いてしまう。 あなたは魔王の優秀な部下として、それでもなお勇者をできるだけ長く足止めできるような改造計画を立ててほしい。 

$ N\times N $ マスの魔王城がある。 一番左上のマスの座標を $ (0,0) $ とし、そこから下方向に $ i $ マス、右方向に $ j $ マス進んだ先のマスの座標を $ (i,j) $ とする。 各マスは空きマス `.` または障害物 `#` のいずれかである。 また、 $ N\times N $ の範囲外はすべて障害物であるとみなす。 マス $ (0,0) $ には入口があり、マス $ (N-1,N-1) $ には玉座がある。 これらのマスはいずれも空きマスである。 あなたは勇者が侵入してくる前に、城内に **扉** と **スイッチ** を設置できる。 #### 扉 扉には $ 0,1,\ldots,2K-1 $ の $ 2K $ 個の **型** がある。 以降、型 $ g $ の扉を単に **扉 $ g $** と呼ぶ。 扉は、上下左右に隣接する 2 マスの間に設置でき、合計で最大 $ M $ 枚まで設置できる。 同じ 2 マスの間に設置できる扉は高々 1 枚である。 同じ型の扉を複数枚設置してもよい。 #### スイッチ スイッチには $ 0,1,\ldots,K-1 $ の $ K $ 個の **種類** がある。 以降、種類 $ k $ のスイッチを単に **スイッチ $ k $** と呼ぶ。 スイッチは各マスに 1 つまで設置できる。 同じ種類のスイッチを異なるマスに複数個設置してもよい。 また、1 つも設置されない種類のスイッチがあってもよい。 入口 $ (0,0) $ や玉座 $ (N-1,N-1) $ にもスイッチを設置してよい。 #### 扉とスイッチの連動 各 $ k=0,1,\ldots,K-1 $ について、扉 $ 2k $ と扉 $ 2k+1 $ はスイッチ $ k $ によって制御される。 同じ型の扉はすべて同じ開閉状態を共有する。 初期状態では、扉 $ 2k $ は開いており、扉 $ 2k+1 $ は閉じている。 スイッチ $ k $ が押されるたびに、扉 $ 2k $ と扉 $ 2k+1 $ の開閉状態が入れ替わる。 すなわち、スイッチ $ k $ が押された回数が偶数回である状態では、扉 $ 2k $ が開き、扉 $ 2k+1 $ が閉じている。 スイッチ $ k $ が押された回数が奇数回である状態では、扉 $ 2k $ が閉じ、扉 $ 2k+1 $ が開いている。 障害物マスとの間に扉を設置してもよいが、そのような扉を通る移動はできない。 障害物マスにスイッチを設置してもよいが、そのようなスイッチは押すことができない。 #### 勇者の行動 城の改造を終えると、勇者が入口 $ (0,0) $ から侵入してくる。 勇者は毎ターン、以下の 2 種類の行動から 1 つを選んで実行できる。 1. 上下左右に隣接する空きマスへ移動する。ただし、現在いるマスと移動先のマスの間に扉があり、かつその扉が閉じている場合、その方向へは移動できない。 2. 現在いるマスにスイッチがある場合、そのスイッチを押す。 現在いるマスにスイッチがある場合でも、勇者は必ずしもそのスイッチを押す必要はない。 スイッチを押さずに隣接マスへ移動してもよい。 勇者は、あなたが設置した扉とスイッチの配置をすべて知っている。 玉座へ到達可能であるならば、勇者は可能な限り少ない行動回数で玉座に到達する。 あなたの目的は、勇者が入口から玉座へ到達するために必要な最小の行動回数をできるだけ大きくすることである。 #### 補足: 勇者の最小行動回数について 出力された改造計画に対する最小行動回数 $ T $ は、状態を「現在位置」と「各スイッチ $ k $ について、スイッチ $ k $ が押された回数の偶奇」の組として幅優先探索を行うことで計算できる。 現在位置は高々 $ N^2 $ 通りであり、各スイッチの状態は $ K $ ビットで表せるため $ 2^K $ 通りである。 したがって、 $ T $ の計算は $ O(2^K N^2) $ 時間で可能である。 以下は python による最小行動回数計算の実装例である。 ``` from collections import deque def calc_T(N, K, c, door_h, door_v, switch): """ N: 盤面サイズ K: スイッチの種類数 c: マップ。c[i][j] は '.' または '#' door_h: 上下方向の扉。door_h[i][j] は (i,j) と (i+1,j) の間の扉の型。扉なしは -1 door_v: 左右方向の扉。door_v[i][j] は (i,j) と (i,j+1) の間の扉の型。扉なしは -1 switch: switch[i][j] はマス (i,j) に置かれたスイッチの種類。スイッチなしは -1 返り値: 入口 (0,0) から玉座 (N-1,N-1) へ到達するための最小行動回数。 到達不能な場合は 0 を返す。 """ def is_open(g, mask): """型 g の扉が、状態 mask において開いているかを返す。""" if g == -1: return True k = g // 2 return ((mask >> k) & 1) == (g & 1) dist = [[[-1] * N for _ in range(N)] for _ in range(1

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ c_0 $ $ \vdots $ $ c_{N-1} $ - すべてのテストケースにおいて、盤面サイズ $ N $ は $ 20 $ に固定されている。 - すべてのテストケースにおいて、設置できる扉の最大枚数 $ M $ は $ 50 $ に固定されている。 - すべてのテストケースにおいて、スイッチの種類数 $ K $ は $ 10 $ に固定されている。 - $ c_i $ は長さ $ N $ の文字列であり、その $ j $ 文字目 $ c_{i,j} $ はマス $ (i,j) $ が空きマスの場合 `.`、障害物の場合 `#` である。 - $ c_{0,0}=c_{N-1,N-1}= $ `.` である。 - すべての空きマスは、空きマスのみを通って入口 $ (0,0) $ から到達可能であることが保証されている。

まず、設置する扉の枚数を $ D $ として、以下の形式で扉の配置を標準出力へ出力せよ。 > $ D $ $ d_0 $ $ i_0 $ $ j_0 $ $ g_0 $ $ \vdots $ $ d_{D-1} $ $ i_{D-1} $ $ j_{D-1} $ $ g_{D-1} $ $ a $ 番目の扉は、向き $ d_a $ 、座標 $ (i_a,j_a) $ 、扉の型 $ g_a $ によって表される。 - $ d_a=0 $ の場合、マス $ (i_a,j_a) $ とマス $ (i_a+1,j_a) $ の間に扉 $ g_a $ を設置する。 - $ d_a=1 $ の場合、マス $ (i_a,j_a) $ とマス $ (i_a,j_a+1) $ の間に扉 $ g_a $ を設置する。 出力は以下の条件を満たさなければならない。 - $ 0\leq D\leq M $ - 各扉について、 $ d_a $ は 0 または 1 である。 - 各扉について、 $ 0\leq g_a

### 得点 出力した改造計画に対して、勇者が入口 $ (0,0) $ から玉座 $ (N-1,N-1) $ へ有限回の行動で到達可能である場合、そのために必要な最小の行動回数を $ T $ とする。 このとき、以下の得点が得られる。 \\\[ \\mathrm{round}\\left(10^6\\times \\log\_2 \\frac{T}{N}\\right) \\\] 勇者が玉座へ到達不能である場合、得点は $ 1 $ 点となる。 合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定が WA や TLE となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 $ N=20 $ , $ M=50 $ , $ K=10 $ で固定である。 まず、すべてのマスが空きマスである状態から開始する。 $ (0,0) $ と $ (N-1,N-1) $ 以外の $ N^2-2 $ マスをランダムな順に並べ、順に以下の処理を行う。 > 対象のマスを $ (i,j) $ とする。 マス $ (i,j) $ の上下左右 4 マスのうち、障害物であるマスの個数が 3 以上であれば、このマスに対する処理をスキップする。 ただし、 $ N\times N $ の範囲外は障害物として数える。 そうでない場合、マス $ (i,j) $ を一時的に障害物に変更する。 この変更によって空きマス全体が非連結になった場合、マス $ (i,j) $ を空きマスに戻す。 非連結にならなかった場合は、マス $ (i,j) $ を障害物にしたままにする。 次に、すべての障害物マスをランダムな順に並べ、順に以下の処理を行う。 > 対象のマスを $ (i,j) $ とする。 マス $ (i,j) $ の上下左右 4 マスに空きマスが 1 つ以上ある場合、マス $ (i,j) $ を空きマスに変更する。 障害物マスを空きマスに変更した回数が $ N $ 回に達した時点で、この処理を終了する。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc067/BpPfrS30.html?lang=ja): ローカル版より高性能でアニメーション表示が可能です。 - [ローカル版](https://img.atcoder.jp/ahc067/BpPfrS30.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc067/BpPfrS30_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。