AT_chokudai005_a カラフルパネル

[problemUrl]: https://atcoder.jp/contests/chokudai005/tasks/chokudai005_a 縦 $ N $ 個、横 $ N $ 個の正方形上にならんだ $ N\ ×\ N $ 個のパネルがあります。あなたは、このパネルを使ってゲームを行います。 このゲームは、出来るだけ全てのパネルの色を $ 1 $ 色に揃える事が目的です。最初、各パネルは、色 $ 1 $ から 色 $ K $ の $ K $ 色で塗られています。 好きな色を念じながら $ 1 $ つのパネルをタッチすることで、そのパネルを好きな色に変えることができます。タッチしたパネルの色を $ i $、変えたい色を $ j $ とします。 この時、タッチしたパネルから、上下左右に隣接する色 $ i $ のパネルだけを辿って到達できる全てのパネルは、色 $ j $ に変化します。 このゲームの最終得点は、以下のような計算式で求められます。 - 最も多いパネルの色を $ i $ とすると、色 $ i $ のパネルが $ 1 $ 枚存在するごとに、$ 100 $ 点を得る。 - パネルを $ 1 $ 回タッチするごとに $ 1 $ 点を失う。 - ただし、パネルを合計 $ 10000 $ 回より多くタッチすると、システムが壊れてしまうため、$ 0 $ 点となる。 パネルの初期状態が与えられます。タッチの仕方を出力し、出来るだけ多くの得点を獲得してください。 なお、この問題は、入力が全て公開されており、また、全ての入力に独立な通し番号idがついています。これを利用して問題を解いても構いません。 また、[C++によるジャッジ上で実際に動いている入出力チェッカー](https://img.atcoder.jp/chokudai005/chekcer.zip)も公開しています。こちらを利用しても構いません。

> id $ N $ $ K $ $ S_1 $ $ S_2 $ : $ S_N $

以下のフォーマットで出力せよ。ただし、$ Q $ はパネルをタッチする回数を表し、$ Y_i,\ X_i,\ C_i $ はそれぞれ、$ i $ 番目にタッチするパネルが、上から $ Y_i $ 番目、左から $ X_i $ 番目(以下、$ (Y_i,\ X_i) $ と表す)であり、変える色が $ C_i $ であることを表す。 > $ Q $ $ Y_1 $ $ X_1 $ $ C_1 $ $ Y_2 $ $ X_2 $ $ C_2 $ : $ Y_Q $ $ X_Q $ $ C_Q $ $ 50 $ 個のテストケースに対する点数の和が、あなたの提出の得点となる。

### 制約 - $ 1 $ ≦ id ≦ $ 50 $ - $ N $ = $ 100 $ - $ K $ = $ 9 $ - $ S_i $ は $ N $ 文字の文字列であり、 $ j $ 番目の文字 $ S_{i,j} $ は、`1`~`K` の $ K $ 種類である。これは、上から $ i $ 番目、左から $ j $ 番目(以下$ (i,j) $と表す）のパネルが$ S_{i,j} $ 色であることを表す。 - $ S $ に使われる文字は、`1`~`K`まで、均等な確率で独立にランダムで選ばれる。 - 入力は[このリンクから得られるzipファイル](https://atcoder.jp/img/chokudai005/dataset.zip)と同一のものが与えられる。 ### Sample Explanation 1 この入力は、説明のため、実際には存在しない小さい入力を使用しております。 パネルは、初期状態では以下のようになっています。 !\[初期状態\](https://atcoder.jp/img/chokudai005/pic1.png) ここから出力の通りに $ 2 $ 回タッチします。 最初は、$ (5,5) $ のパネルを色 $ 1 $ に変えます。この時、隣接するパネルの中で、元のパネルの色である、色 $ 2 $ のものは存在しないため、このパネルのみの色が変わります。 !\[状態1\](https://atcoder.jp/img/chokudai005/pic2.png) 次に、$ (5,2) $ のパネルの色を $ 1 $ に変えます。この時、上下左右に隣接した色 $ 3 $ のパネルを辿って到達できる全てのパネルは、色 $ 1 $ に変化するため、以下のようにパネルが変化します。 !\[状態2\](https://atcoder.jp/img/chokudai005/pic3.png) 全てのパネルを操作した後、最も多い色のパネルは色 $ 1 $ であり、この枚数は $ 18 $ 枚です。 よって、$ 18\ ×\ 100\ -\ 2\ =\ 1798 $ 点が、この解の答えになります。