AT_abc345_d [ABC345D] Tiling

题目描述

有一个由边长为 $1$ 的方格组成的 $H$ 行 $W$ 列的网格，以及 $N$ 块瓷砖。
第 $i$ 块瓷砖（$1 \leq i \leq N$）是 $A_i \times B_i$ 的矩形。
请判断是否可以将这些瓷砖按照以下所有条件铺在网格上。

• 所有的格子都恰好被 $1$ 块瓷砖覆盖。
• 可以有瓷砖未被使用。
• 使用的瓷砖可以旋转或翻转后放置。但每块瓷砖必须与网格线对齐，且不能超出网格范围。

输入格式

输入以如下格式从标准输入读入。

$N$ $H$ $W$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

如果可以按照题目要求将瓷砖铺在网格上，输出 Yes；否则输出 No。

输入输出样例 #1

输入 #1

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

输出 #1

Yes

输入输出样例 #2

输入 #2

1 1 2
2 3

输出 #2

No

输入输出样例 #3

输入 #3

1 2 2
1 1

输出 #3

No

输入输出样例 #4

输入 #4

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

输出 #4

No

说明/提示

限制条件

• $1 \leq N \leq 7$
• $1 \leq H, W \leq 10$
• $1 \leq A_i, B_i \leq 10$
• 输入均为整数

样例解释 1

使用第 $2,4,5$ 块瓷砖，可以如下图所示铺放，使得每个格子恰好被 $1$ 块瓷砖覆盖。

因此，输出 Yes。

样例解释 2

无法将瓷砖放置在网格内而不超出边界。
因此，输出 No。

样例解释 3

无法用瓷砖覆盖所有格子。
因此，输出 No。

样例解释 4

请注意，所有格子都必须恰好被 $1$ 块瓷砖覆盖。

由 ChatGPT 4.1 翻译