← 返回题目列表

AtCoder · awtf2024_e

E. 彩色邮票

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

分数: 2000 点

问题陈述

解决以下问题 T 测试用例。

有一块板 N 行和 N 列。让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。最初,所有细胞都是无色的。

你有 N^2 邮票。对于每对整数 (h,w) (1 \leq h,w \leq N),有一张尺寸为的邮票 h \times w,称为邮票 (h,w)。所有邮票都有不同的颜色。

“按下邮票 (h,w)”表示以下操作:

  • 选择位置 (a,b) (1 \leq a \leq N-h+1,\ 1 \leq b \leq N-w+1)。然后给所有单元格上色 (i,j) (a \leq i \leq a+h-1, b \leq j \leq b+w-1) 与印章的颜色 (h,w)。如果单元格已经着色,则颜色将被覆盖。

您的目标是将每个图章精确地按一次,以便最终板上的所有单元格都具有不同的颜色。

您已经按下 K 邮票。的 i第一个按下的邮票是 (H_i,W_i),其位置为 (A_i,B_i).

显示按剩余的一种方法 N^2-K 邮票以实现目标。 在此问题中,仅向您提供输入,您可以通过按适当的顺序和位置按下剩余的印章来实现目标。

约束

  • 1 \leq T
  • 2 \leq N \leq 400
  • 0 \leq K < N^2
  • 1 \leq H_i,W_i \leq N
  • 1 \leq A_i \leq N-H_i+1
  • 1 \leq B_i \leq N-W_i+1
  • (H_i,W_i) \neq (H_j,W_j) (i \neq j)
  • 总和 N^2 跨单个输入的所有测试用例不超过 400^2.
  • 仅向您提供输入,您可以通过按适当的顺序和位置按下剩余的印章来实现目标。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
case_1
case_2
\vdots
case_T

每个测试用例均按以下格式给出:

N K
H_1 W_1 A_1 B_1
H_2 W_2 A_2 B_2
\vdots
H_K W_K A_K B_K

输出

对于每个测试用例,按以下格式打印答案:

h_1 w_1 a_1 b_1
h_2 w_2 a_2 b_2
\vdots
h_{N^2-K} w_{N^2-K} a_{N^2-K} b_{N^2-K}

这意味着 i要按下的第一个印章(不包括已经按下的印章) K 邮票)是 (h_i,w_i),其位置是 (a_i,b_i).


示例输入 1

4
2 2
2 2 1 1
1 2 2 1
2 0
3 3
3 3 1 1
3 2 1 2
2 3 1 1
5 15
5 5 1 1
4 5 2 1
5 4 1 1
4 4 2 1
3 5 3 1
2 5 4 1
1 5 4 1
5 3 1 1
3 4 3 1
2 4 3 1
4 3 2 1
1 4 4 1
3 3 3 1
2 3 4 1
1 3 5 1

示例输出 1

2 1 1 1
1 1 2 1

2 2 1 1
2 1 1 1
1 2 1 1
1 1 1 1

2 2 1 2
3 1 1 2
1 3 2 1
1 2 2 1
2 1 1 2
1 1 1 2

5 2 1 1
4 2 1 1
3 2 1 1
5 1 1 1
2 2 1 1
4 1 1 1
1 2 1 1
3 1 1 1
2 1 1 1
1 1 1 1

考虑第一个测试用例。

如果我们让 i 表示颜色 i- 第一个按下的印章(包括已经按下的印章) K 邮票),板子变化如下:

..     ->      11     ->      11     ->      31     ->      31
..  (2,2,1,1)  11  (1,2,2,1)  22  (2,1,1,1)  32  (1,1,2,1)  42

请注意,示例输出包含额外的换行符以提高可读性,但您不需要打印这些换行符(尽管如果您愿意,也可以这样做)。