AT_c_league2026_2_a Slide into Place

$ N\times N $ マスの盤面がある。 左上のマスの座標を $ (0,0) $ とし、そこから下方向に $ i $ マス、右方向に $ j $ マス進んだ先のマスの座標を $ (i,j) $ とする。 最初、すべてのマスは空である。 各マスには、駒を置きたい目標マスであるかどうかが指定されている。 あなたは、次の操作を $ N^2 $ 回以下行うことができる。 盤面の上下左右いずれかの辺と、その辺に対応する行または列を選び、盤外から駒を $ 1 $ 個入れる。 駒を最初に入れるマスを入口と呼ぶ。 各方向の入口と駒の進行方向は以下の通りである。 選ぶ辺 行または列 入口 進行方向 左 行 $ i $ $ (i,0) $ 右 右 行 $ i $ $ (i,N-1) $ 左 上 列 $ j $ $ (0,j) $ 下 下 列 $ j $ $ (N-1,j) $ 上 入口に既に駒がある操作は行えない。 駒は入口から進行方向へまっすぐ進み、次のマスに既に駒があるか、次のマスが盤外であるとき、現在のマスで停止して固定される。 進行方向に対して横に隣接するマスに駒があっても停止しない。 固定された駒を動かしたり、取り除いたりすることはできない。 各操作は、入れた駒が固定された後に次の操作へ進む。 目標マスに置かれた駒を増やし、それ以外のマスに置かれた駒を抑えて、得点ができるだけ高くなるような操作列を求めよ。 #### 操作の例 説明のため、 $ N=4 $ の盤面での操作例を示す。 実際の入力では $ N=30 $ である。 水色のマスは目標マス、緑の駒は目標マスに置かれた駒、赤の駒はそれ以外のマスに置かれた駒を表す。 図中の $ t $ は操作回数、駒の数字は入れた順番であり、紫の矢印と輪は直前の駒の進路と停止位置を表す。 初期状態と3回の操作後の盤面 1. 左から行 $ 1 $ へ駒を入れると、盤面の端の $ (1,3) $ で停止する。 2. 上から列 $ 2 $ へ駒を入れると、 $ (3,2) $ で停止する。 途中で $ (1,3) $ の駒の横を通るが、停止しない。 3. 下から列 $ 3 $ へ駒を入れると、 $ (1,3) $ の駒の手前の $ (2,3) $ で停止する。 この後、右から行 $ 1 $ へ駒を入れる操作は、入口 $ (1,3) $ に既に駒があるため行えない。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ s_0 $ $ \vdots $ $ s_{N-1} $ 各値は以下の制約を満たす。 - $ N=30 $ - $ s_i $ は長さ $ N $ の文字列であり、各文字は `o` または `.` である。 $ s_i $ の $ j $ 文字目はマス $ (i,j) $ が目標マスであるかどうかを表し、`o` なら目標マス、`.` ならそれ以外のマスである。 ここで、文字列の文字の位置も $ 0 $ 始まりとする。

以下の形式で標準出力に出力せよ。 > $ d_0 $ $ k_0 $ $ \vdots $ $ d_{K-1} $ $ k_{K-1} $ ここで、 $ K $ は出力する操作の回数であり、 $ N^2 $ 以下でなければならない。 各 $ t=0,\ldots,K-1 $ について、 $ d_t $ と $ k_t $ は $ t $ 番目の操作を表す整数であり、 $ 0\leq d_t\leq 3 $ 、 $ 0\leq k_t

### 得点 すべての操作を終えたとき、駒が置かれていない目標マスの個数を $ E $ 、目標マス以外に置かれた駒の個数を $ B $ とする。 このとき、以下の得点が得られる。 \\\[ S=N^2-E-B+1 \\\] 上の例で $ 3 $ 回の操作を終えた時点では、 $ E=2 $ 、 $ B=1 $ なので、得点は $ 4^2-2-1+1=14 $ となる。 合計で 100 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定が WA や TLE となり、提出の得点は 0 点となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 $ N=30 $ とする。 実数 $ p $ を区間 $ [0.35,0.65] $ から一様ランダムに選ぶ。 各マスを互いに独立に確率 $ p $ で目標マスとし、それ以外のマスは目標マスでないものとする。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/c-league2026-2/RqpYgVXL.html?lang=ja): ローカル版より高性能でアニメーション表示と手動プレイが可能です。 - [ローカル版](https://img.atcoder.jp/c-league2026-2/RqpYgVXL.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 コンパイルが通らない場合は `rustup update` をお試し下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/c-league2026-2/RqpYgVXL_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、チーム外とのビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。 ご注意下さい。