← 返回题目列表

AtCoder · chokudai005_a

A. 彩色面板

中文机器翻译题面 查看原题

問題文

縦 N 個、横 N 个托盘上排列着 N × N 个面板。你将使用这些面板来进行游戏。

这个游戏的目标是尽可能将所有面板的颜色 1 调整成相同的颜色。最开始,每个面板的颜色是 1 从 颜色 K 的 K 被颜色涂上。

一边想着自己喜欢的颜色 1 触摸面板,就可以将该面板变为自己喜欢的颜色。触摸的面板颜色为 i,想要变成的颜色为 j 。 此时,从触摸的面板出发,只能沿着上下左右相邻的颜色 i 面板到达的所有面板,其颜色将 j 发生变化。

该游戏的最终得分可以通过以下计算公式来求得。

  • 假设最多的面板颜色为 i ,颜色 i 的面板每存在 1 块,100 得 分。
  • 每触摸 1 次面板, 1 会失去 分。
  • 但是,如果总共触摸面板超过 10000 次,系统将会损坏,因此得分为0 分。

将给出面板的青少年状态。请输出触摸方式,尽可能获得更多得分。

此外,该问题的输入均已公开,并且每个输入都有独立的序号 id,可利用此信息来解决问题也可以。

另外,我们也公开了在C++上实际运行的输入输出检查器。使用这个也是可以的。

制約

  • 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到,均匀且独立随机选出的正确率。
  • 输入是 有一条从这个rinkku获得的zipfeiru会得到相同的东西。

入力

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

0 6 9
515795
153859
833597
333419
333121
533917

出力例 1

2
5 5 1
5 2 1

这个输入仅用于说明,实际上使用的是较小的输入。

面板的初始状态如下所示。

初期状態

从这里开始,按照输出进行操作 触摸 2 次。

首先, 为(5,5) 面板着色 将其更改为 1 。此时,相邻面板中的颜色即为原面板的颜色 没有 2 ,所以只有这个面板会改变颜色。

状態1

接下来,(5,2) 面板颜色 将其更改为 1 。此时,上、下、左、右相邻的颜色 按照 3 面板可到达的所有面板均已着色 1 ,因此面板变化如下所示。

状態2

操作完所有面板后,颜色最多的面板是 1 这个号码是 18 件。

因此,18 × 100 - 2 = 1798 点就是这个解决方案的答案。