分数: 800 点
问题陈述
有一个网格 H 行和 W 列,其中单元格位于 i从顶部开始的第行和 j从左边算起的第列表示为 (i,j)。网格仅在单元格中有孔 (r,c)。我们将使用几块瓷砖来平铺所有没有孔的单元格。给你非负整数 N 和 M 这样 H \times W=L \times (N+M)+1。 一块瓷砖 1 行和 L 列称为水平图块,并且图块为 L 行和 1 列称为垂直图块。 确定是否存在精确使用平铺的方法 N 水平瓷砖和 M 垂直瓷砖不旋转,如果存在的话也会显示一种这样的方式。 有关输出格式和更精确条件的详细信息,请检查输出部分。
解决 T 每个输入文件的测试用例。
约束
- 1 \leq T \leq 5
- 1 \leq H \leq 1000
- 1 \leq W \leq 1000
- 2 \leq H \times W
- 2 \leq L \leq 1000
- 0 \leq N
- 0 \leq M
- 1 \leq r \leq H
- 1 \leq c \leq W
- H \times W=L \times (N+M)+1
- 总和 N+M 所有测试用例最多 6\times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个案例均按以下格式给出:
H W L N M r c
输出
按以下格式输出答案:
output_1 output_2 \vdots output_T
在这里, output_t 表示输出 t- 第一个测试用例。
对于每种情况,如果可以满足条件的平铺,则让 (A_i,B_i) 是被覆盖的最左边的单元格 i第一个水平瓷砖和 (C_j,D_j) 是被覆盖的最上面的单元格 j第一个垂直平铺,并按以下格式输出:
Yes A_1 B_1 A_2 B_2 \vdots A_N B_N C_1 D_1 C_2 D_2 \vdots C_M D_M
更准确地说,输出整数序列 A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_N) 长度 N 和 C=(C_1,C_2,\dots,C_M),D=(D_1,D_2,\dots,D_M) 长度 M 满足以下所有条件:
- 联盟 \{(A_i,B_i+l)\mid i=1,2,\dots,N,\;l=0,1,\dots,L-1\}, \{(C_j+l,D_j)\mid j=1,2,\dots,M,\;l=0,1,\dots,L-1\},和 \{(r,c)\} 等于 \{(h,w)\mid h=1,2,\dots,H,\;w=1,2,\dots,W\}.
请注意,由于约束 H \times W=L \times (N+M)+1,当此条件成立时,图块不会彼此重叠。
如果无法满足条件,则输出 No.
示例输入 1
3 1 3 2 1 0 1 1 1 3 2 1 0 1 2 3 3 2 1 3 1 1
示例输出 1
Yes 1 2 No Yes 3 2 2 1 1 2 1 3
在第三个测试用例中,左上角的单元格中有一个洞。可以按如下方式平铺:
┌─┬─┐ ┌─┤ │ │ │ ├─┴─┤ └─┴───┘