← 返回题目列表

AtCoder · pakencamp_2019_day2_a

A. Paken君的涂色书

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

配点: 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) 的值确定如下。 按照
    1. i = 1, 2, 3, ..., Q 的顺序执行操作2.至4.。
    2. 首先,r_i 在 1 以上 N 从以下整数中均匀随机选择。
    3. 接下来, 满足c_i 在 1 以上 N-K+1 从以下整数中均匀随机选择。
    4. r_i=r_j 和 满足 |c_i - c_j| \leq K-1 如果 1 以上 i-1 的整数 j 存在,则返回2。 重新确定 (r_i, c_i) 。如果没有,请返回 1. 并执行以下操作 对 i 的值进行运算。

入出力例

输入和输出示例是这个链接 可以从下载。

请注意,这些示例也包含在实际测试用例中,并将计入分数的一部分。