AT_pakencamp_2020_day2_h 旅立ちの日に

[problemUrl]: https://atcoder.jp/contests/pakencamp-2020-day2/tasks/pakencamp_2020_day2_h あなたと kaage 君(以降「あなたたち」とする)は、$ N*N $ のグリッド上において、二人組になって自転車でオリエンテーリングをしている。グリッドの上から(0-indexed で) $ i $ 行目、左から(0-indexed で) $ j $ 列目のマスは $ (i,j) $ と表される。以下に示されるオリエンテーリングのルールのもと、オリエンテーリングの終了時の「スコア」をなるべく高くすることが、あなたたちの目的である。 - あなたたちは、時刻 $ 0 $ にマス $ (sx,sy) $ を出発する。 - オリエンテーリングをするフィールドは、$ 0\leq\ i,j\

入力は以下の形式で標準入力から与えられる。 > \\(N\\) \\(T\\) \\(M\\) \\(sx\\) \\(sy\\) \\(S\_1\\) \\(S\_2\\) \\(S\_3\\) \\(v\_{0,0}\\) \\(v\_{0,1}\\) \\(\\cdots\\) \\(v\_{0,N-1}\\) \\(\\vdots\\) \\(v\_{N-1,0}\\) \\(v\_{N,1}\\) \\(\\cdots\\) \\(v\_{N-1,N-1}\\) $ Mission_1\\ Mission_2\\ \vdots\\ Mission_M $ \\(v\_{i,j}\\) は `.` であるか、`-` であるかのいずれかである。$ v_{i,j} $ が `.` のときマス $ (i,j) $ が「陸」であることを、`-` のとき「海」であることを表す。 また、$ Mission_i $ はミッションを表し、それぞれ次のような形式である。 ``` \(1\) \(x_i\) \(y_i\) ``` ミッション $ 1 $ を表し、訪れるべきマスは $ (x_i,y_i) $ である。 ``` \(2\) \(x_i\) \(y_i\) ``` ミッション $ 2 $ を表し、訪れるべきマスは $ (x_i,y_i) $ である。 > \\(3\\) \\(k\_i\\) \\(x\_{i,1}\\) \\(y\_{i,1}\\) \\(x\_{i,2}\\) \\(y\_{i,2}\\) $ \vdots $ \\(x\_{i,k\_i}\\) \\(y\_{i,k\_i}\\) ミッション $ 3 $ を表し、訪れるべきマスは $ (x_{i,1},\ y_{i,1}),(x_{i,2},y_{i,2}),\cdots,(x_{i,k_i},y_{i,k_i}) $ である。

あなたたちは、すべての $ 1\leq\ i\leq\ T $ について、オリエンテーリング開始 $ i $ 分後にそれぞれ二人がいるマス目の位置を、 $ i $ 行目に空白区切りで出力しなければならない。ただし、題意に反するような移動をした場合、この問題におけるあなたの得点は $ 0 $ 点となり、`WA` になる。例として、$ i $ 分後におけるあなたのいるマスが $ (x_{i,A},y_{i,A}) $, kaage 君のいるマスが $ (x_{i,B},y_{i,B}) $ のとき、$ i $ 行目の出力は次のようになる。 ``` \(x_{i,A}\) \(y_{i,A}\) \(x_{i,B}\) \(y_{i,B}\) ```

### 制約 - 入力は $ v_{i,j} $ を除きすべて整数である。 - $ N=201 $ - $ sx=sy=100 $ - $ T=10000 $ - $ M=1000 $ - $ S_1=5,S_2=4,S_3=7 $ - \\(v\_{i,j}\\) は `.` であるか、`-` であるかのいずれかである。 - $ 1\leq\ k_i\ \leq\ 5 $ - $ 0\leq\ x_i,x_{i,j},y_i,y_{i,j}\leq\ 200 $ - $ (x_i,y_i),(x_{i,j},y_{i,j}),(sx,sy) $ は「陸」のマスである。 - $ (sx,sy) $ から海のマスを通らずにすべての海以外のマスに到達できる。 - 「陸」のマスはフィールド全体の半分以上を占める。 ### テストケースの生成方法 テストケースは全部で $ 20 $ 個あり、これらは次に示すアルゴリズムで生成される。 1. $ N*N $ のグリッドを考える。$ [0,N) $ から一様ランダムに $ x_i,y_i $ を、$ [0,70] $ から一様ランダムに $ h_i $ を選び、 $ (x,y) $ を中心として高さ $ h_i $ の山を構成してグリッドに足す。具体的には、$ (x,y) $ には $ max(0,\ h_i-|x_i-x|-|y_i-y|) $ が加算される。 2. 1. の操作を合計 $ 50 $ 回繰り返す。 3. 2. でできたグリッドに対し、あるマスの数を $ X $ としたとき、$ X\ なら「海」、そうでなければ「陸」とする。 $ 4. 3. でできたグリッドが制約を満たさない場合、1. に戻る。制約を満たせば、これが出力するグリッドとなる。 5. $ M $ 個のミッションを生成する。ミッション番号は $ [1,3] $ から一様ランダムに選ばれ、ミッション $ 3 $ の座標の個数は $ [1,5] $ から一様ランダムに選ばれる。座標は、「陸」のマス全体から一様ランダムに選ばれる。 また、[開発用ファイル](https://img.atcoder.jp/pakencamp-2020-day2/distribution.zip)を配布しているので、そちらも参照すること。 ### 採点 あなたのこの問題での得点は、$ 20 $ 個のテストケースに対する得点の和を $ 80 $ で割って小数点以下を切り捨てた値となる。