AT_rco_contest_2017_qual_a Multiple Pieces

[problemUrl]: https://atcoder.jp/contests/rco-contest-2017-qual/tasks/rco_contest_2017_qual_a 同じ大きさの正方形のマスが $ H $ 行 $ W $ 列並んだ長方形のグリッドがあります。$ 1\ \leq\ i\ \leq\ H,\ 1\ \leq\ j\ \leq\ W $ を満たす整数 $ i $ と $ j $ について、 $ i $ 行 $ j $ 列に位置するマスの座標を $ (i,\ j) $ と表します。各マスには `0` 以上 `9` 以下の整数が 1 つ書かれています。 このグリッド上で、いくつかのピースを作ります。ピースとは、ちょうど $ K $ 個のマスからなる、グリッド上の領域です。 ピース内のマス同士は互いに連結でなければいけません。マス同士が連結しているというのは、ピース内の全てのマスの組について、ピース内で縦橫に接続したマスを辿って互いに到達可能であることをいいます。 ピースは可能な限りいくつでも作ることができますが、あるピースを作るために使用したマスは、別のピースを作るために使用することはできません。 各ピースはスコアを持ちます。ピースが含むマスに書かれた $ K $ 個の整数の積が、そのピースのスコアになります。全てのピースのスコアの合計値を最大化してください。

入力は以下の形式で標準入力から与えられます。 > $ H $ $ W $ $ K $ $ s_1 $ $ s_2 $ : $ s_H $ - $ H $ はグリッドの行数を表す整数であり、$ H\ =\ 50 $ を満たします。 - $ W $ はグリッドの列数を表す整数であり、$ W\ =\ 50 $ を満たします。 - $ K $ は 1 つのピースを作るマスの数を表す整数であり、$ K\ =\ 8 $ を満たします。 - $ s_i\ (1\ \leq\ i\ \leq\ H) $ はグリッドの $ i $ 行目を表す長さ $ W $ の文字列であり、 $ s_i $ を構成する文字はいずれも `0` から `9` までの整数です。 $ s_i $ の $ j\ (1\ \leq\ j\ \leq\ W) $ 文字目は、グリッドにおける $ (i,\ j) $ のマスの整数を表します。

出力は以下の形式で標準出力に出力してください。 > $ C $ $ y_{1,1} $ $ x_{1,1} $ $ y_{1,2} $ $ x_{1,2} $ : $ y_{1,K} $ $ x_{1,K} $ $ y_{2,1} $ $ x_{2,1} $ $ y_{2,2} $ $ x_{2,2} $ : $ y_{C,K} $ $ x_{C,K} $ - 1 行目にピースの数 $ C $ を出力してください。 - 続く $ C\ \times\ K $ 行には、各行にスペース区切りで、マスの位置を表す 2 つの整数を出力してください。 - $ (c\ -\ 1)\ \times\ K\ +\ k\ (1\ \leq\ c\ \leq\ C\ ,\ 1\ \leq\ k\ \leq\ K) $ 番目には、$ c $ 個目のピースで使われている $ k $ 個目のマスの位置 $ (y_{c,k},\ x_{c,k}) $ の行と列を、スペース区切りで順番に出力してください。 - 同じピースで使われているマスは連続して出力してください。 - 同じピースで使われているマスは、どのような順番で出力しても構いません。 - 同じピースで使われているマスは、ちょうど $ K $ 個を出力してください。 - 同じピースで使われているマスは、連結している必要があります。 - 各ピースはどのような順番で出力しても構いません。

### 背景 ※この「**背景**」の項に書かれている文章は問題とあまり関係がありません。問題文は「**問題文**」の項から始まります。 20XX 年、RCO 量子サーバールーム ━━━ ここには RCO の持つ大量の量子コンピュータが所狭しと並んでいる。 2016 年に量子コンピューティングに参入した RCO アドテク部は、2017 年には実際の量子コンピュータ上で機械学習プログラムを走らせたり、量子アニーリングの国際学会のホストを務めるなどして勢いを増し、この時代では量子コンピュータ専門の企業になっていた。 競技プログラミングの経験を買われて入社した社員 X は、広告マッチングシステムの高速化に携わっていたが、今やその仕事も量子コンピュータに取って代わられ、プログラミングの仕事を失った彼は量子コンピュータを接続する仕事をしている。 RCO の長年の研究によって、量子コンピュータには以下の性質があることが明らかになった。 - 量子コンピュータは $ K $ 台連結することによって、その力を発揮する。 $ K $ 台より多くても少なくても機能しない。この連結した $ K $ 台を「ピース」と呼ぶ。 - あるピースに含まれる量子コンピュータは、別のピースに含むことができない。 - ピースのもつ力は、ピース内の各量子コンピュータの能力の積に等しい。 このサーバールームには $ H $ 行 $ W $ 列のグリッド状に $ H\ \times\ W $ 台の量子コンピュータが並んでいて、社員 X の仕事は、どの量子コンピュータを接続するか決めることである。量子コンピュータは、辺で接している隣の量子コンピュータとしか接続できない。接続された量子コンピュータを辿って到達できる時、それらの量子コンピュータは連結であるといえる。 社員 X は適切にピースを作ることで、全てのピースの力の合計を最大化したいが、プログラミングの仕事を失った彼はプログラミング能力も失ってしまった！そこで、彼の親しい友人であるあなたが、そのプログラムを書いてあげることにした。 ### 制約 - $ H\ =\ 50 $ - $ W\ =\ 50 $ - $ K\ =\ 8 $ - 各テストケースは、各マスに書かれる整数が一様乱数によってマスごとに独立に $ 0 $ 以上 $ 9 $ 以下の整数が入るように生成されます。 ### 採点について 各テストケースについて、出力されたピースのスコアの合計値を 10,000 で割り、小数点以下を切り上げた整数が、そのテストケースの得点になります。 テストケースは全部で 10 個あります。各テストケースの得点の合計値が、この問題の得点になります。 ### ジェネレータとテスター ジェネレータとテスターを次のリンクから提供しています。 [ジェネレータ・テスター](https://gist.github.com/tomerun/3eb426f32321dff164d3aa7e817bf3b5) ### ビジュアライザ 入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。 - このビジュアライザは主要なブラウザ上で動作確認を行っていますが、全ての環境で動作することを保証していません。 - このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。 - このビジュアライザを使用したことで発生したトラブルには対応できません。ご了承ください。 ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。 [ビジュアライザ](https://gist.github.com/tomerun/945734b2301017cb29e123d3491669fc) ### Sample Explanation 1 この結果は、下の図のようになります。 !\[\](https://atcoder.jp/img/rco-contest-2017-qual/a-sample.jpg)1 個目のピースのスコアは、$ 1\ \times\ 5\ \times\ 3\ \times\ 2\ \times\ 2\ \times\ 3\ \times\ 3\ \times\ 3\ =\ 1620 $ より 1620 です。 2 個目のピースのスコアは、$ 0\ \times\ 3\ \times\ 4\ \times\ 7\ \times\ 4\ \times\ 9\ \times\ 0\ \times\ 0\ =\ 0 $ より 0 です。 よって、このテストケースの得点は $ (1620+0)/10000=0.1620 $ の、小数点以下を切り上げて 1 となります。