/ 
Time Limit: 10 sec / Memory Limit: 1024 MB
背景
※この「背景」の項に書かれている文章は問題とあまり関係がありません。問題文は「問題文」の項から始まります。
20XX 年、RCO 量子サーバールーム ━━━ ここには RCO の持つ大量の量子コンピュータが所狭しと並んでいる。
2016 年に量子コンピューティングに参入した RCO アドテク部は、2017 年には実際の量子コンピュータ上で機械学習プログラムを走らせたり、量子アニーリングの国際学会のホストを務めるなどして勢いを増し、この時代では量子コンピュータ専門の企業になっていた。
競技プログラミングの経験を買われて入社した社員 X は、広告マッチングシステムの高速化に携わっていたが、今やその仕事も量子コンピュータに取って代わられ、プログラミングの仕事を失った彼は量子コンピュータを接続する仕事をしている。
RCO の長年の研究によって、量子コンピュータには以下の性質があることが明らかになった。
- 量子コンピュータは K 台連結することによって、その力を発揮する。 K 台より多くても少なくても機能しない。この連結した K 台を「ピース」と呼ぶ。
- あるピースに含まれる量子コンピュータは、別のピースに含むことができない。
- ピースのもつ力は、ピース内の各量子コンピュータの能力の積に等しい。
このサーバールームには H 行 W 列のグリッド状に H \times W 台の量子コンピュータが並んでいて、社員 X の仕事は、どの量子コンピュータを接続するか決めることである。量子コンピュータは、辺で接している隣の量子コンピュータとしか接続できない。接続された量子コンピュータを辿って到達できる時、それらの量子コンピュータは連結であるといえる。
社員 X は適切にピースを作ることで、全てのピースの力の合計を最大化したいが、プログラミングの仕事を失った彼はプログラミング能力も失ってしまった！そこで、彼の親しい友人であるあなたが、そのプログラムを書いてあげることにした。
問題文
同じ大きさの正方形のマスが H 行 W 列並んだ長方形のグリッドがあります。1 \leq i \leq H, 1 \leq j \leq W を満たす整数 i と j について、 i 行 j 列に位置するマスの座標を (i,\ j) と表します。各マスには 0 以上 9 以下の整数が 1 つ書かれています。
このグリッド上で、いくつかのピースを作ります。ピースとは、ちょうど K 個のマスからなる、グリッド上の領域です。 ピース内のマス同士は互いに連結でなければいけません。マス同士が連結しているというのは、ピース内の全てのマスの組について、ピース内で縦橫に接続したマスを辿って互いに到達可能であることをいいます。
ピースは可能な限りいくつでも作ることができますが、あるピースを作るために使用したマスは、別のピースを作るために使用することはできません。
各ピースはスコアを持ちます。ピースが含むマスに書かれた K 個の整数の積が、そのピースのスコアになります。全てのピースのスコアの合計値を最大化してください。
制約
- H = 50
- W = 50
- K = 8
- 各テストケースは、各マスに書かれる整数が一様乱数によってマスごとに独立に 0 以上 9 以下の整数が入るように生成されます。
入力
入力は以下の形式で標準入力から与えられます。
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 個を出力してください。
- 同じピースで使われているマスは、連結している必要があります。
- 各ピースはどのような順番で出力しても構いません。
採点について
各テストケースについて、出力されたピースのスコアの合計値を 10,000 で割り、小数点以下を切り上げた整数が、そのテストケースの得点になります。
テストケースは全部で 10 個あります。各テストケースの得点の合計値が、この問題の得点になります。
入力例1
50 50 8 53201047392344411470438731252072209638476606576022 13242641632370617792332244270350675420864470404947 76372756316250650550563212732102937351075767336672 43391440260272522122049404306241926052045602433410 52720091423022222223344046324704721322132522334463 61693424425167321660472564434627234092497347246494 74134790436364436322363453027722019104342653173246 06407501031023661315440613726761261950342364317750 32434003036734297520344434846325625906542524345344 05729429300314444521730193634776225440322622762751 86170432967422452264329256425612350934624120326541 26260636676449250472787131576465747405632235055443 40432921056447267224144437767405026230355213327648 24472704922530039761140156512267320526045880236176 07436062226225795544236739634472433612487916576911 55028479331202644253542466261627757154341742036422 44736123293411696555237251437134202024002321292635 81006264110473511002519270476632234036184209203337 34270476462376904464776536713540006776077721473323 32686034469090324371414045247233600414023574431213 04080796152524541314625733207636637252102345120474 36904177763204264504704640313204912205748211284652 57646677253297155293792204031260531495473582235447 61433022620013614311260112334301203542233443703533 26244220666366257106223555253272744437143551534343 72304587152225442705443405915460720321040950035230 47266334792647716333950266050273713405293544063606 42436560231720147179723145056172462274137306344833 67443441401341276340150714410757027270244643654052 40404753669203250556387534301404004772563702525335 33666140790372604312034023231462405523170203279455 28102241646055944326071031547720270757259214611268 87746061343006140377547262199332060353244672704332 41225292920224383122136357428437525343572422270572 92160034046626479600394426924399953726374944127112 34214633560182413271544514253244940522222796462242 90062659764619121220592222437422113522730203122504 62132594362434364325233673235334175411672571335787 73620117121304602302723930343349513021441324772513 17763541417154976777536460213763760329204066378655 63263664266374779346744404484544692004111522323332 44632343821194331534223464082067723522091642446477 19604176094424473236373041633400242226774002570136 26233643026251007443132567680196513234006280452006 56654403268971142737776260023025532206663443245553 03675233864254722764052295365207973334724257032549 26647441241535162193323334617330476964344433334454 72463395769420225214343614245237240974142331159757 14226384625321023247202066906229042200415265466217 22420733370592047743255351070026772752224341534396
出力例1
2 1 1 2 1 1 2 1 3 2 3 3 3 4 3 4 2 5 5 6 5 7 5 8 5 9 5 10 5 11 5 12 5
この結果は、下の図のようになります。
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 となります。
ジェネレータとテスター
ジェネレータとテスターを次のリンクから提供しています。
ビジュアライザ
入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。
- このビジュアライザは主要なブラウザ上で動作確認を行っていますが、全ての環境で動作することを保証していません。
- このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
- このビジュアライザを使用したことで発生したトラブルには対応できません。ご了承ください。
ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。