分数: 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
请注意,示例输出包含额外的换行符以提高可读性,但您不需要打印这些换行符(尽管如果您愿意,也可以这样做)。