配点: 1 \ 700 \ 000 点
問題文
研君以国际涂色奥林匹克为目标,每天都在努力涂色。
现在,为了制作涂色作品,他准备了 N \times N 的方格。在这些方格上,从 i 行开始,从左数, j 行的格子记作 (i, j) 。特别地,左上角的格子是 (1, 1),右下角的格子是 (N, N) 。
。他将每个格子涂上颜色 1,色 2,色 3,...,色 K 的 K 我决定用颜色来上色。不过,也可以有不涂颜色的格子。
这时,完成的涂色画必须满足以下条件。
-
1 \leq i \leq K 满足的所有整数 i 对于这些整数,必须满足以下条件。
- 色 i 用颜色涂的格子 1 在存在至少……个的情况下,颜色 i 涂的所有格子是连通的。
- 也就是说,颜色 i 涂的不同 2 个格子 (x_1, y_1), (x_2, y_2) 考虑它们时,无论是哪种 ((x_1, y_1), (x_2, y_2)) 组合,从格子 (x_1, y_1) 到格子 (x_2, y_2) 之间,只能沿上下左右相邻的有颜色格子通行。 i 只能沿着的格子前进。
例如,像图(A)、图(B)那样的涂色画满足条件,但图(C)因为被颜色 1 涂的格子整体不是连通的,所以不满足条件。
另外,完成的涂色画将按照以下方式进行积分评定。
- 马斯 (i, j) 被颜色 A_{i, j} 涂的格子数量记为 V_1 。
- 马斯 (r_i, c_i),(r_i, c_i+1),(r_i, c_i+2),...,(r_i, c_i+K-1) 在 1,色 2,色 3,...,色 K 中,以颜色 1 涂的格子有i 个, (1 \leq i \leq Q) 在 V_2 。
- 则涂色画的积分为100 \times V_2 + V_1 点。不满足条件的涂色画的积分为 0 点。
此时,请将格子涂色以尽可能获得更高的积分。
制約
- N = 100
- Q = 240
- K = 4
- 1 \leq A_{i,j} \leq K
- 1 \leq r_i \leq N
- 1 \leq c_i \leq N - K + 1
- r_i = r_j (i \neq j) 时,|c_i - c_j| \geq K 满足。
- 所有输入均为整数。
入力
输入将以以下格式从标准输入提供.
N K Q
A_{1,1} A_{1,2} ... A_{1,N}
A_{2,1} A_{2,2} ... A_{2,N}
:
A_{N,1} A_{N,2} ... A_{N,N}
r_1 c_1
r_2 c_2
:
r_Q c_Q
出力
请按以下格式输出。 (N 跨线输出。 )
S_{1, 1} S_{1, 2} S_{1, 3} ... S_{1, N}
S_{2, 1} S_{2, 2} S_{2, 3} ... S_{2, N}
S_{3, 1} S_{3, 2} S_{3, 3} ... S_{3, N}
:
S_{N, 1} S_{N, 2} S_{N, 3} ... S_{N, N}
但是,S_{i, j} 是一个质量 指示要绘制的颜色 (i, j) 。鳟鱼 (i, j) 着色 使用 x 绘画时,S_{i, j} = x ,如果没有涂漆, S_{i, j} = 0 。
另外,违反上述格式的输出,0 \leq S_{i, j} \leq K 的输出或不满足问题文本中着色条件的输出将被判定为“不正确”。在这种情况下,如果测试用例作为输入示例给出,则该测试用例的分数为 0 点。对于其他测试用例,除了输入示例之外的所有测试用例 0 点。
测试用例生成方法
- A_{i, j} 的值为1 以上 K 从以下整数中均匀随机选择。
-
(r_i, c_i) 的值确定如下。
按照
- i = 1, 2, 3, ..., Q 的顺序执行操作2.至4.。
- 首先,r_i 在 1 以上 N 从以下整数中均匀随机选择。
- 接下来, 满足c_i 在 1 以上 N-K+1 从以下整数中均匀随机选择。
- r_i=r_j 和 满足 |c_i - c_j| \leq K-1 如果 1 以上 i-1 的整数 j 存在,则返回2。 重新确定 (r_i, c_i) 。如果没有,请返回 1. 并执行以下操作 对 i 的值进行运算。
入出力例
输入和输出示例是这个链接 可以从下载。
请注意,这些示例也包含在实际测试用例中,并将计入分数的一部分。