AT_ahc050_a [AHC050A] Gamble on Ice

$ N \times N $ のマス目からなるスケートリンクがある。左上のマスの座標を $ (0,0) $ とし、下方向に $ i $ マス、右方向に $ j $ マス進んだ位置のマスの座標を $ (i,j) $ とする。 $ N \times N $ マスの外部はすべて岩で覆われており、侵入できない。初期状態では、 $ M $ 個のマスに岩が置かれている。 このスケートリンクと 1 体のロボットを使って次のゲームを行う。 - ゲーム開始時、あなたの獲得賞金は $ 0 $ 円である。 - はじめに、あなたは岩の置かれていない $ N^2 - M $ マスを任意の順番で並べた列 $ P = ( P_0,P_1,\dots,P_{N^2 - M - 1} ) $ を宣言する。 - 次に、岩の置かれていないマスの中から一様ランダムに $ 1 $ つが選択され、そこにロボットが配置される。 - その後、 $ i = 0,1,\dots,N^2 - M - 1 $ の順に以下を繰り返す。 - まず、ロボットが上下左右の $ 4 $ 方向のうち $ 1 $ つを一様ランダムに選択する。 - 次に、ロボットがその方向に岩にぶつかるまで直線的に進行する。 - ロボットが $ 1 $ マスも動かない場合もあることに注意せよ。 - その後、マス $ P_i $ に岩を置く。 - そのマスにロボットがあった場合、ロボットが潰されてゲームが終了する。 - そのマスにロボットがなかった場合、あなたは $ 1 $ 円を獲得する。 最終的に獲得できる賞金の期待値ができるだけ大きくなるような列 $ P $ を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ S_{0,0} \dots S_{0,N-1} $ $ \vdots $ $ S_{N-1,0} \dots S_{N-1,N-1} $ - 全てのテストケースにおいて、 $ N=40 $ に固定されている。 - $ M $ は $ N^2/10 $ 以上 $ N^2/4 $ 以下の整数である。 - $ S_{i,0} \dots S_{i,N-1} $ は `#.` からなる $ N $ 文字の文字列であり、 $ S_{i,j} $ が `#` なら初期状態でマス $ (i,j) $ に岩が置かれていることを、 `.` なら初期状態でマス $ (i,j) $ には岩が置かれていないことを表す。

求めた列 $ P $ のうち $ P_i=(x_i,y_i) $ としたとき、以下の形式で標準出力に出力せよ。 > $ x_0 $ $ y_0 $ $ \vdots $ $ x_{N^2 - M - 1} $ $ y_{N^2 - M - 1} $ このとき、列 $ P $ は以下の制約を満たす必要がある。 - 全ての $ P_i $ は相異なる。 - 全ての $ P_i $ について、初期状態においてマス $ P_i $ に岩が置かれていない。 [例を見る](https://img.atcoder.jp/ahc050/k1BmZE1o.html?lang=ja&seed=0&output=sample)

### 得点 最終的に獲得できる賞金の期待値を $ E $ とする。このとき、 $ \displaystyle {\rm round} \left ( \frac{10^6 \times E}{N^2 - M - 1} \right ) $ の得点が得られる。 合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 - まず、 $ N=40 $ とする。 - 次に、 $ M $ を $ N^2/10 $ 以上 $ N^2/4 $ 以下の整数から一様ランダムに選出する。 - 最後に、 $ N^2 $ 個のマスから相異なる $ M $ 個を一様ランダムに選び、選ばれたマスに岩を置くことでマス目の初期状態を定める。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc050/k1BmZE1o.html?lang=ja): ローカル版より高性能でアニメーション表示と手動プレイが可能です。 - [ローカル版](https://img.atcoder.jp/ahc050/k1BmZE1o.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc050/k1BmZE1o_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。