← 返回题目列表

AtCoder · joi2025_yo2_a

A. 美纹纸胶带

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

配点: 100 点

問題文

参考:https://atcoder.jp/contests/joi2023yo2/tasks/joi2023_yo2_c

JOI 正在使用纸和遮蔽胶带进行着色。

纸张为矩形且垂直。 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.pdf

JOI,你可以用这张纸和胶带 执行 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).
  • 所有输入值均为整数。

小課題

  1. (32 点) H = 2,W = 2,q_k = 1 (1 \leqq k \leqq Q).
  2. (32 点) q_k = 1 (1 \leqq k \leqq Q).
  3. (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 满足约束。