配点: 100 点
問題文
参考:https://atcoder.jp/contests/joi2023yo2/tasks/joi2023_yo2_cJOI 正在使用纸和遮蔽胶带进行着色。
纸张为矩形且垂直。 H 行,横 W 绘制了列网格。从上面 i 行目 (1 \leqq i \leqq H),从左起 j 列目 (1 \leqq j \leqq W) 它被称为 (i, j) 。
每个方块都有一种颜色。 1 颜色用整数表示,所有方块的颜色初始为 0 。
参考:https://github.com/jcioi/2022-sp-sprinkler/blob/main/task/statement.pdfJOI,你可以用这张纸和胶带 执行 Q 操作。 运算 k 回目 (1 \leqq k \leqq Q) 是一个整数 根据 q_k 的值解释如下。
- q_k = 1 ,这个运算是一个整数 它由 x_k, y_k, c_k 表示。鳟鱼 (x_k, y_k), (x_k + 1, y_k), (x_k, y_k + 1), (x_k + 1, y_k + 1) 对于每个方块,如果方块没有用遮蔽胶带覆盖,则更改方块的颜色。 将其更改为 c_k 。如果某个方块被遮蔽胶带覆盖,则不要对该方块进行任何操作。 用遮蔽胶带覆盖
- q_k = 2 ,这个运算是一个整数 它由 x_k, y_k 表示。鳟鱼 (x_k, y_k), (x_k + 1, y_k), (x_k, y_k + 1), (x_k + 1, y_k + 1) 。
Q 完成操作后,撕掉所有遮蔽胶带。此外,当您从某个方块上撕下遮蔽胶带时,该方块的颜色将与覆盖遮蔽胶带之前的颜色相同。
Q 编写一个程序,根据有关操作次数的信息,找到纸上所有方块的最终颜色。 是
制約
- 2 \leqq H \leqq 500.
- 2 \leqq W \leqq 500.
- 1 \leqq Q \leqq 200 \: 000.
- q_k 是 给出了 1 或 2 ( 当1 \leqq k \leqq Q).
- q_k = 1 时,1 \leqq x_k \leqq H - 1,1 \leqq y_k \leqq W - 1,1 \leqq c_k \leqq 10^9 (1 \leqq k \leqq Q).
- q_k = 2 时,1 \leqq x_k \leqq H - 1,1 \leqq y_k \leqq W - 1 (1 \leqq k \leqq Q).
- 所有输入值均为整数。
小課題
- (32 点) H = 2,W = 2,q_k = 1 (1 \leqq k \leqq Q).
- (32 点) q_k = 1 (1 \leqq k \leqq Q).
- (36 点)没有额外的限制。
入力
输入按以下格式给出。
H W Q (Query \: 1) (Query \: 2) \vdots (Query \: Q)
各 (Query \: k) (1 \leqq k \leqq Q) 包含多个以空格分隔的整数。这几天之一 第 1 个整数是 q_k ,并且该行的内容是以下之一。
- q_k = 1 ,此行后面是 3 整数 给出 x_k, y_k, c_k 用空格分隔。
- q_k = 2 ,此行后面是 2 整数 给出 x_k, y_k 用空格分隔。
出力
更改最终纸张上所有方块的颜色。 输出 H 行。i 行目 (1 \leqq i \leqq H)有W 以空格分隔的整数。在这里, 输出到j 番目 (1 \leqq j \leqq W) 的整数是一个质量 将颜色设置为 (i, j) 。 让我们按顺序看一下
入力例 1
5 5 4 1 2 2 1 2 1 2 2 3 3 1 1 3 5
出力例 1
0 0 0 5 0 0 1 1 5 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
4 操作。
1 关于操作,q_1 = 1 。鳟鱼 (2, 2),(2, 3),(3, 2),(3, 3) 并未全部用遮蔽胶带覆盖,因此您可以更改颜色。 更改为 1 。
此时,论文如下所示:
0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
2 关于操作,q_2 = 2 。鳟鱼 (1, 2),(1, 3),(2, 2),(2, 3) 。
此时,纸张看起来是这样的: 另外,在代表用遮蔽胶带覆盖的正方形颜色的整数右侧,
添加了 * 。
0 0* 0* 0 0 0 1* 1* 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
3 关于操作,q_3 = 2 。鳟鱼 (3, 3),(3, 4),(4, 3),(4, 4) 。
此时,论文如下所示:
0 0* 0* 0 0 0 1* 1* 0 0 0 1 1* 0* 0 0 0 0* 0* 0 0 0 0 0 0
4 关于操作,q_4 = 1 。鳟鱼 (1, 4),(2, 4) 没有用遮蔽胶带覆盖,因此您可以更改颜色。 将其更改为 5 。鳟鱼 (1, 3),(2, 3) 上覆盖着遮蔽胶带,因此请勿对其进行任何操作。
此时,论文如下所示:
0 0* 0* 5 0 0 1* 1* 5 0 0 1 1* 0* 0 0 0 0* 0* 0 0 0 0 0 0
因此,最终纸张上所有方块的颜色如输出示例所示。
这个输入/输出示例是一个小任务。 3 满足约束。
入力例 2
5 5 3 1 1 1 2 1 3 3 3 1 2 4 2
出力例 2
2 2 0 0 0 2 2 0 2 2 0 0 3 2 2 0 0 3 3 0 0 0 0 0 0
这个输入/输出示例是一个小任务。 2, 3 满足约束。
入力例 3
10 10 10 2 5 7 2 5 6 1 5 6 1 1 9 2 1 2 1 1 1 2 4 2 2 3 2 1 2 2 3 1 9 9 2 1 8 8 1
出力例 3
0 0 0 0 0 0 0 0 0 0 0 0 3 2 2 0 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1 1 2 0 1 1 0 0 0 0 0 2 2
这个输入/输出示例是一个小任务。 3 满足约束。