← 返回题目列表

AtCoder · arc203_e

E. 一孔瓷砖网格

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

分数: 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

在第三个测试用例中,左上角的单元格中有一个洞。可以按如下方式平铺:

  ┌─┬─┐
┌─┤ │ │
│ ├─┴─┤
└─┴───┘